PDF de programación - Tema 6: Ordenación (Parte 2) - Estructuras de datos

1

Estructuras de datos

2

Tema 6: Ordenación (Parte 2)

Javier Miranda

Nivel de

Abstracción

Alto

Bajo

Estructura de datos

Pila, Cola, Lista, Árbol, Hash, Grafo

Array, Lista Enlazada, Árbol

18-feb-04

(C) Javier Miranda

18-feb-04

Ordenación

(C) Javier Miranda

3

4

NO RECURSIVOS

Contenido

• Métodos avanzados de ordenación:

– No recursivos

• Shell (Donald L. Shell, 1959).

– Recursivos
• Mergesort
• Quicksort (C. Hoare, 1962)

• Resumen

18-feb-04

(C) Javier Miranda

18-feb-04

(C) Javier Miranda

Shell

• Diseñado por Donald L. Shell en 1959.
• Basado en ordenación por inserción
• Objetivo:

– Reducir el número de copias necesarias para

colocar los elementos.

5

6

Repaso del método de
ordenación por inserción

Run

18-feb-04

(C) Javier Miranda

18-feb-04

(C) Javier Miranda

1

Applet del método de

ordenación Shell

Run

7

Shell Sort

8

procedure Shell_Sort (Tabla : in out T_Tabla) is

Salto : Natural;

begin

-- Calcular el valor inicial del salto
. . .
while Salto > 0 loop

Ordenar_Por_Insercion (Tabla, Salto);
-- Calcular el nuevo salto
. . .

end loop;

end Shell_Sort;

18-feb-04

(C) Javier Miranda

18-feb-04

(C) Javier Miranda

Elección del Salto

Análisis

9

10

• Propuesta original de Donald .L. Shell en 1959

– Salto/2

• Propuestas alternativas:

– Salto / 2.2 y el valor 1 cuando el salto es menor que 2.2)
– (5*Salto-1) / 11 y el valor 1 cuando es menor que 5)
– etc.

• La mejor (Donald E. Knuth)

– A partir de la serie recursiva: Salto = Salto*3 + 1

1 4 13 40 121 364 etc.

• Nadie ha sido capaz aún de calcular de forma
teórica su eficiencia en el caso general (sólo
casos particulares).
• O(N3/2) . . O(N7/6)

Orden

Inserción

O(N2)

Shell

Shell

O(N3/2)

O(N7/6)

10
Elem.
100
32
14

100
Elem.
10.000
1000
215

1000
Elem.

1.000.000
32.000
3.200

10000
Elem.
1.000.000
1.000.000
46.000

18-feb-04

(C) Javier Miranda

18-feb-04

(C) Javier Miranda

11

Fusión (“Merge”)

12

procedure Fusion (Resultado : in out T_Tabla;
T_Tabla;
T_Tabla);

Tabla_A : in
Tabla_B : in

RECURSIVOS

18-feb-04

(C) Javier Miranda

18-feb-04

(C) Javier Miranda

2

Merge Sort

procedure Merge_Sort (Tabla : in out T_Tabla;

Primero : in Natural;
Ultimo : in Natural) is

Medio : Natural := (Primero + Ultimo) / 2;

if Primero >= Ultimo then

begin

return;

else

Merge_Sort (Tabla, Primero, Medio);
Merge_Sort (Tabla, Medio + 1, Ultimo);
Fusion (Tabla, Tabla (Primero .. Medio),

Tabla (Medio + 1 .. Ultimo) );

13

14

Applet del método

de fusión (MergeSort)

Run

end if;

end Merge_Sort;

18-feb-04

(C) Javier Miranda

18-feb-04

(C) Javier Miranda

Antes de ver el método

QuickSort vamos a ver en qué

consiste el “particionado”

15

16

Particionado

• División de la información en dos grupos:

– Los menores que un determinado valor.
– Los mayores que ese valor.

• Al elemento que se utiliza para hacer la

división se le suele llamar “pivote”

• Ejemplo de uso:

– Dividir la clase en dos grupos: los menores de

19 años y los mayores.

18-feb-04

(C) Javier Miranda

18-feb-04

(C) Javier Miranda

Applet del método
de particionado

17

Run

18-feb-04

(C) Javier Miranda

procedure Partition_Version_1 (Tabla : in out T_Tabla;
Primero: in
Natural;
Ultimo : in Natural;
Pivote : in

Natural) is

18

P : Natural := Primero;
U : Natural := Ultimo;

begin
loop

while P<U and then Tabla(P)<Pivote loop

P := P + 1;

end loop;
while U<P and then Tabla(U)>Pivote loop

U := U - 1;

end loop;
exit when P >= U;
Intercambiar (Tabla, P, U);

end loop;

end Partition_Version_1;

18-feb-04

(C) Javier Miranda

3

function Partition_Version_2
(Tabla : in out T_Tabla;
Primero: in
Natural;
Ultimo : in Natural)
return Natural

is

while Tabla(P)<Pivote loop

P := P + 1;

end loop;

Pivote : Natural :=

Tabla (Ultimo);
P : Natural := Primero;
U : Natural := Ultimo - 1;

begin
loop

19

Algoritmo de QuickSort

20

while U>P and then

Tabla(U)>Pivote loop

U := U - 1;

end loop;
exit when P >= U;
Intercambiar (Tabla, P, U);

end loop;
Intercambiar (Tabla, P,Ultimo);
return P; -- Posicion definitiva

-- del pivote.
end Partition_Version_1;

procedure Quick_Sort (Tabla : in out T_Tabla;

Primero : in Natural;
Ultimo : in Natural) is

begin

if Primero >= Ultimo then

return;

else

Pos_Pivote := Particion_Version2 (Tabla, Primero, Ultimo);
Quick_Sort (Tabla, Primero, Pos_Pivote – 1)
Quick_Sort (Tabla, Pos_Pivote + 1, Ultimo)

end if;

end Quick_Sort;

18-feb-04

(C) Javier Miranda

18-feb-04

(C) Javier Miranda

Applet del método

QuickSort

Run

21

22

Resumen

• Shell es fácil de implementar y es bueno para
arrays no demasiado grandes (varios miles de
datos).

• En general Quicksort es más rápido.

• Algunos expertos recomiendan utilizar siempre

primero Shell y sólo utilizar Quick cuando
realmente sea necesario.

18-feb-04

(C) Javier Miranda

18-feb-04

(C) Javier Miranda

4