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

Imágen de pdf Tema 6: Ordenación (Parte 2) - Estructuras de datos

Tema 6: Ordenación (Parte 2) - Estructuras de datosgráfica de visualizaciones

Publicado el 16 de Julio del 2020
51 visualizaciones desde el 16 de Julio del 2020
104,6 KB
4 paginas
Creado hace 16a (18/02/2004)
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
  • Links de descarga
http://lwp-l.com/pdf17912

Comentarios de: Tema 6: Ordenación (Parte 2) - Estructuras de datos (0)


No hay comentarios
 

Comentar...

Nombre
Correo (no se visualiza en la web)
Valoración
Comentarios...
CerrarCerrar
CerrarCerrar
Cerrar

Tienes que ser un usuario registrado para poder insertar imágenes, archivos y/o videos.

Puedes registrarte o validarte desde aquí.

Codigo
Negrita
Subrayado
Tachado
Cursiva
Insertar enlace
Imagen externa
Emoticon
Tabular
Centrar
Titulo
Linea
Disminuir
Aumentar
Vista preliminar
sonreir
dientes
lengua
guiño
enfadado
confundido
llorar
avergonzado
sorprendido
triste
sol
estrella
jarra
camara
taza de cafe
email
beso
bombilla
amor
mal
bien
Es necesario revisar y aceptar las políticas de privacidad