algoritmica parte ii: algoritmos existentes 3... · 2019-10-01 · 5 escuela tÉcnica superior de...
Post on 23-Mar-2020
4 Views
Preview:
TRANSCRIPT
PARTE II: Algoritmos existentes
Eugenio Fco. Sánchez Úbeda
Cristina Puente ÁguedaUniversidad Pontificia Comillas
ALGORITMICA
- 1
Algoritmos de ordenación
2ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Ordenación
• Operación básica, se utiliza en casi todos los programas
complejos
• Existen muchos algoritmos
3ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Algoritmos de ordenación
• Entrada: conjunto de objetos a ordenar
• Salida: secuencia ordenada de objetos
• Objetivo de la ordenación:
– Facilitar la búsqueda de elementos en el conjunto ya
ordenado
• Existen multitud de algoritmos para realizar lo mismo, cada
uno con ciertas ventajas e inconvenientes
• Principal restricción: Espacio necesario en memoria RAM.
– Si los datos caben: ordenación interna
– Si no caben: ordenación externa
AlgoritmoEntradas Salidas
4ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Clasificación de los algoritmos de ordenación
• Ordenación interna: Arrays en memoria RAM• Ordenación externa: Ficheros secuenciales (discos, cintas)
Ordenación interna
Ordenación externa
Todas las tarjetas están visibles Sólo visibles las tarjetas superiores
Ordenación Interna
RAM
CPU
Datos a ordenar
Algoritmo
Auxiliar
RAM
CPU
Algoritmo
I/O
Almacenamiento secundario
Almacenamiento p rimario
(externo)
Ordenación Externa
Datos a ordenar
5ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Algoritmos de ordenación externa (I)
• La información a ordenar no cabe toda al mismo tiempo en
memoria RAM
– La estrategia a utilizar es muy diferente
• Dos diferencias importantes con la ordenación interna:
– El coste de acceso a un elemento es ahora varios ordenes de
magnitud superior que cualquier cálculo en CPU
– Restricción severa de acceso a los elementos, dependiente del tipo
de almacenamiento secundario utilizado.
• Limitar los movimientos entre el almacenamiento externo y
la memoria principal
RAM
Fichero de datos a ordenar
6ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Algoritmos de ordenación externa (II)
• Idea:
– Trabajar con varios dispositivos adicionales (discos, cintas) para
guardar operaciones intermedias
• Fases:
– Generación de tramos (división+distribución)
• Trocear el fichero inicial en bloques de datos ordenados (tramos)
• Guardar los tramos en dispositivo externo auxiliar
– Mezcla de tramos
• Fundir los tramos en sucesivas pasadas hasta tener un único tramo
MezclaDivisión
+ Distribución
Cinta 1
Cinta 3
Cinta 2
Datos a ordenar
Bloque ordenado o "Tramo"
Cintas disponibles
7ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Algoritmos de ordenación interna
• Métodos directos (simples)– Basados en inserción
• Inserción directa, binaria
– Basados en selección
• Selección directa
– Basados en intercambio
• Intercambio directo (burbuja y sacudida)
• Métodos sofisticados– Basados en inserción
• Algoritmo de Shell
– Basados en selección
• ´Montículo (Heapsort)
– Basados en intercambio
• Rápido (Quicksort)
Ordenación “in situ”: se ordena sin utilizar otro array del mismo tamaño
8ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Algoritmos simples vs. sofisticados
• ¿Por qué tiene interés un
algoritmo simple si los hay
mejores (los sofisticados)?
• Para invertir una matriz
puede compensar utilizar el
ordenador pero para sumar
26+14 quizá es demasiada
molestia encenderlo
9ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Tipos de algoritmos según su comportamiento
• Natural/antinatural
– Cuando tarda lo mínimo posible si ya está ordenado y lo máximo
cuando está en orden inverso
• Estable/intestable
– Cuando el orden relativo de los elementos con la misma clave de
ordenación no se altera
• Simétrico/asimétrico
– Cuando cuesta lo mismo ordenar 2341 que 5123
• Correcto/incorrecto
– Cuando siempre encuentra la solución correcta
– Es "lo típico"
Campo 1 1 3 4 3 5 4 3
Campo 2 20 10 10 20 30 40 10
Campo 1 1 3 3 3 4 4 5
Campo 2 20 10 20 10 10 40 30
Campo 1 1 3 3 3 4 4 5
Campo 2 20 10 10 20 10 40 30
Ordenación estable
Ordenación inestable
Campo clave utilizado en la ordenación
10ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Algoritmos de ordenación interna: estructuras
• Lo normal es utilizar una array de registros
A:
1 N
A(k) ó A[k]
Nombre
Apellidos
Edad
DNI
R.Edad
R.Nombre
R.Apellidos Registro R con 4 campos
R.DNI
Lo normal es ordenar por uno de los campos, el
denominado campo “clave”: A(k).clave
11ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Inserción directa (I)
• Idea
• Utilizando un vector de registros y ordenando sobre el
mismo (utilizando espacio auxiliar para un registro):
Espacio disponible en memoria
2 1 8695
12ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Inserción directa (II)
12 1 8695A={ }
2 8695ordenado por ordenar
2 869
i=2
i=3, carta=1
i=3,j=25i=3j=2
2 8692 5 i=3,j=1
1 8692 5ordenado por ordenar
Inserta carta
Busca posición
Selecciona carta
5
• Ejemplo
13ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Inserción directa (III)
A = InserciónDirecta(A, N) %A vector de registros a ordenar, N: nº de registros
1 For i=2 to N
carta = A[i]; % selecciona última carta
j=i-1; %busca punto de inserción
2 While (j>0 & carta < A[j]) % alternando comparaciones
A[j+1]=A[j]; % y movimientos
j=j-1;
end 2
A[j+1]=carta; % inserta la carta
end 1
Secuencia origen Secuencia destino
BúsquedaSeleccionar el
siguiente
Inserción directa
14ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Inserción directa (IV)
A = InserciónDirectaCentinela(A, N)
1 For i=2 to N
carta = A[i]; % selecciona última carta
j=i-1;
A[0]=carta;
2 While (carta < A[j]) % comparación más sencilla
A[j+1]=A[j];
j=j-1;
end 2
A[j+1]=carta; % inserta la carta
end 1
• Uso de un centinela
– Evita salirse del array simplificando la condición
– Se añade el centinela en el extremo del array para detectar que se
llega al final del mismo
• Nota: Será necesario dimensionar A para tener N+1 elementos
15ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Inserción binaria
• En inserción directa A(1:i-1) ya ordenado
– Mejora en la búsqueda del punto de inserción (mediante bisección)
INSERCIÓN_BINARIA(A)
1 For i=2 to N carta = A[i]; iz=1; de = i-1; 2 While iz de m = floor[(iz+de)/2]; If (carta < A[m]) then de = m-1; else iz = m+1; end 2 3 For j=i-1 to iz step -1 A[j+1]=A[j]; end 3 A[iz]=carta;end 1
21 86 95
iz de
7
m
%mueve items(hace huecopara carta)
i-1iz
A = InserciónBinaria (A, N)
Zona ya ordenada
16ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Selección directa (I)
• Idea
Secuencia origen Secuencia destino
Búsqueda
Secuencia origen Secuencia destino
Búsqueda Insertar en el siguiente
Seleccionar el siguiente
Inserción directa
Selección d irecta
17ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Selección directa (II)
A={ }Secuencia origendestino
(ya ordenado) (por ordenar)
i i=N-1i=1
j j=Nj=i+1k Selección
+ Intercambio
A = SelecciónDirecta(A, N) % A vector de registros a ordenar, N: nº de registros
1 For i=1 to N-1 % separación secuencia origen/destino
k=i;
x = A[i]; % inicializa búsqueda mínimo en origen
2 For j=i+1 to N
3 if (A[j]<x) then % busca mínimo en origen
k=j;
x=A[j];
end 3
end 2
A[k]=A[i]; % intercambio, inserta al final
A[i]=x; % de la secuencia destino
end 1
18ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Selección directa (III)
• Ejemplo:
12 1 8695A={ }
2 8695
por ordenar
1 869
i=1
i=1 , k=3 ,x=1k=3i=1
ordenado por ordenar
Intercambia
Selecciona min item
2 5
19ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Mezcla directa (I)
• Utiliza divide y vencerás:
– Divide el array en dos partes más pequeñas
– Se ordenan recursivamente. Si son suficientemente pequeñas se
resuelve directamente
– Se combinan esas soluciones para ordenar finalmente el array
Ya ordenadas
1 2
3
4
5 6 7
8
20ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Mezcla directa (II)
A = MezclaDirecta (A, iz, de)
1 If (iz < de) then % sale si sólo un item
me = floor ( (iz+de)/2 ); % valor entero por debajo de iz
A = MezclaDirecta (A, iz, me); % lado izquierdo
A = MezclaDirecta (A, me+1, de); % lado derecho
A = Mezclar (A, iz, me, de); % Combina dos secuencias ordenadas
end 1
Fin
A = Mezclar (A, iz, me, de)
Fin
Ya ordenadas
1 2
3
4
5 6 7
8iz me
de
21ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Mezcla directa (III)
• Ejemplo
22ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Intercambio directo
• Característica dominante: :
– Intercambio entre pares de elementos
– Mezcla de inserción y selección directa
• IDEA:
– Hacer repetidas pasadas sobre el array ordenando parejas de
elementos contiguos
- +
Intercambio
23ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Intercambio directo: burbuja (I)
A={ }Secuencia or igendestino
(ya ordenado) (por ordenar)
i i=Ni=2
j j=Nj=i
- +
A = IntercambioBurbuja (A, N)
1 For i=2 to N % separación secuencia origen/destino
2 For j=N to i step -1 % mueve de dcha a izq
3 if (A[j-1] > A[j]) then
x = A[j-1];
A[j-1] = A[j]; % intercambio
A[j] = x;
end 3
end 2
end 1
Fin
24ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Intercambio directo: burbuja (II)
• Ejemplo
• Se hacen pasadas inútiles– controlar lo que realmente está ordenado
• Asimetría antinatural – Alternar el sentido de las pasadas
12 1 8695A={ }
2 86 95
por ordenar
i=2
i=2 , j=6 :-1:2
ordenado
mueve 6 y 1
i=3 , j=6 :-1:31 2 86 95mueve 8 y 2
i -1
12 65 1 2 561 pasada 3 pasadas
25ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Intercambio directo: sacudida (I)
A = IntercambioSacudida (A, N)
iz=2; de=N; k=N; % inicializa origen [iz ... de]
1 Repeat
2 For j=de to iz step -1 % movimiento derecha-izquierda
if (A[j-1]>A[j]) then
x=A[j-1]; A[j-1]=A[j]; A[j]=x; k=j;
end 2
iz = k+1; % mueve extremo izq de origen
4 For j=iz to de % movimiento izquierda-derecha
if (A[j-1]>A[j]) then
x=A[j-1]; A[j-1]=A[j]; A[j]=x; k=j;
end 4
de = k-1; % mueve extremo dcha de origen
1 until (iz>de) Fin
A={ }Secuencia origendestino
(ya ordenado) (por ordenar)
iz
j
- + +-
destino(ya ordenado)
de
k
iz'
A={ }origendestino
(ya ordenado)
iz
j
- + +-
destino(ya ordenado)
de
[iz ... de]
Alternancia
26ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Intercambio directo: sacudida (II)
• Ejemplo
• Las mejoras sólo afectan al número de comparaciones
12 1 8695A={ }
2 86 95
por ordenar
iz=2 de=6 k=6
mueve 6 y 1k=2 iz=3 de=6
1 2 86 95mueve 5 y 9k=6 iz=3 de=5
k=6 iz=7 de=51 2 86 95stop
La ordenación por intercambio es inferior a la
ordenación por selección o por inserción
27ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Incrementos decrecientes –Shell- (I)
• Mejora real de Inserción Directa
– Inserción funciona mal con muchos datos
– Inserción trabaja mejor cuando los datos están bastante ordenados
• Concepción curiosa del paradigma “Divide y vencerás”:
– Utilizar Inserción Directa como elemento básico para solucionar
subproblemas
– Llamar a Inserción directa con pocos datos y bastante ordenados
• Agrupar los elementos de p en p y ordenarlos por separado
4 en 4
2 en 2
1 en 1
2 5 85 2 8
1,3,7,15,31...,No se conoce la secuencia de incrementos
mejor, una razonable acabaría así:
28ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Incrementos decrecientes –Shell- (II)
• IDEA básica
Inserción directa
4 2 7 3
4 2 7 3
42 73
agrupar de 3 en 3
• Además las ordenaciones de los distintos grupos para un mismo
incremento se realizan "en paralelo“
29ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Incrementos decrecientes –Shell- (III)
A = IncrementosDecrecientes (A, N, INC, N_INC)
1 For m=1 to N_INC
p = INC[m]; % fija incremento, agrupa de "p en p"
2 For i=p+1 to N % empieza en el "segundo" elemento
carta = A[i];
j=i-p; % el elemento anterior de ese grupo
3 While (j>0 & carta < A[j])
A[j+p]=A[j];
j=j-p;
end 3
A[j+p]=carta;
end 2
end 1
Fin
• Ejemplo de secuencia de incrementos típica (tiene que terminar en 1):
• INC = (9, 5, 3, 1); N_INC = 4;
A = InserciónDirecta(A, N)
1 For i=2 to N
carta = A[i];
j=i-1;
2 While (j>0 & carta < A[j])
A[j+1]=A[j];
j=j-1;
end 2
A[j+1]=carta;
end 1
30ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Incrementos decrecientes –Shell- (IV)
• Ejemplode 4 en 4
85 21 9 743
de 2 en 2
2 53 41 78 9
2 53 41 78 92 53 41 78 9
4 grupos
2 grupos 2 53 41 78 92 53 41 78 92 53 41 78 9
grupo 2
grupo 1
p=4
p=2
grupo 2
grupo 1
grupo 1
i=3
i=4
i=5
i=6
i=7
2 53 41 78 92 53 41 78 9
ordenado1 grupo
p=1
de 1 en 1
31ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Heapsort
Secuencia origen Secuencia destino
Insertar en el siguiente
Secuencia origen Secuencia destino
Insertar en el siguiente
N items
N-1 items
Selección en C=N-1
Selección en C=N-2
Siguiente iter
Selección directa
• Mejora REAL de selección directa:
• TRUCO:
– guardar en cada iteración más información que el elemento mínimo
-> Estructura "montículo"
32ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Heapsort: estructura montículo (I)
25
131512
16 14 19 11
2018
1
2 3
4 5 6 7
8 9 10
25 18 20 16 14 19 11 12 15 131 2 3 4 5 6 7 8 9 10
como árbol binario
como array
Propiedad: Propiedad:
A[2i1]A[i]A[2i] i iz....de /2 A[Padre (i)]A[i] i1
• Montículo:
– Secuencia estructurada ("ordenada") de items en árbol
• Representación + Propiedad (ejemplo):
33ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Heapsort: estructura montículo (II)
• A[1] tiene el elemento de mayor clave
• Funciones elementales (ojo si se programa en C):
• Final del montículo
– Tam_Monti: índice del último elemento del montículo
Tam_Monti ≤ N
Ejemplo:
– Altura de un nodo: número de nodos en el camino hasta la hoja
más alejada del subárbol con raíz en ese nodo
f loor(
19 11
203
6 7
Padre (i) i / 2)Hijo _ izq (i) 2 i
Hijo _ decha (i) 2 i 1
251
Usando A[0] A[N 1]:
Hijo_ izq(i) 2i 1
Hijo_ dcha(i) 2i 2
25
131512
16 14 19 11
2018
1
2 3
4 5 6 7
8 9 10
25 18 20 16 14 19 11 12 15 131 2 3 4 5 6 7 8 9 10
como árbol binario
como array
Propiedad: Propiedad:
A[2i1]A[i]A[2i] i iz....de /2 A[Padre (i)]A[i] i1
34ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Heapsort: Mantener la propiedad (I)
• El poder mantener la propiedad de un montículo en el que
únicamente se modifica el nodo raíz es una pieza clave en
el algoritmo
• IDEA: considerar tres nodos cada vez
• Suposición
– Subárboles hijos 'iz' y 'de' tienen que ser ya montículos
• Versión recursiva o iterativa
i
iz de
Intercambia
Continua comprobando
propiedad
-
+
35ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Heapsort: Mantener la propiedad (II)
A = Monticuliza (A, Tam_Mont, i) % hunde o criba el elemento i
iz=Hijo_izq(i); de = Hijo_dch(i); % hijos tienen que ser ya montículos
1 if (iz ≤ Tam_Mont & A[iz] > A[i]) then% mayor = índice
mayor = iz; % nodo mayor clave
else 1 % entre i, iz y de
mayor = i; % controla salirse con Tam_Mont
end 1
2 if (de ≤ Tam_Mont & A[de] > A[mayor]) then
mayor = de;
end 2
3 if (mayor ≠ i) then % Padre i viola propiedad
x = A[i]; A[i] =A[mayor]; A[mayor] = x; % intercambiar A[i] con A[mayor]
A = Monticuliza (A, Tam_Mont, mayor);
end 3
Fin
36ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Heapsort: Monticuliza (ejemplo)
25
131612
18 14 19 11
2015
1
2 3
4 5 6 7
8 9 10
25
131612
15 14 19 11
2018
1
2 3
4 5 6 7
8 9 10
25
131512
16 14 19 11
2018
1
2 3
4 5 6 7
8 9 10
i
(a) (b)
(c)
i
37ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Heapsort: construye montículo inicial
A = ConstruyeMonticuloInicial (A, N) % Crea el montículo inicial
Tam_Mont = N; % crea un montículo que ocupa todo el array
1 For i= floor(N/2) to 1, step –1 % la mitad dcha de A ya OK
A = Monticuliza (A, Tam_Mont, i);
end 1
Fin
• Se construye de abajo a arriba (árbol)
o de derecha a izquierda (array),
garantizándose que los subárboles de
los hijos son ya montículos
38ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Heapsort: algoritmo de ordenación (I)
• Idea:
Zona DESORDENADA
Zona ORDENADA
La zona ordenada crecerá hacia la izquierda añadiendo el
elemento mayor de la zona desordenada
La zona desordenada disminuye sacando el elemento mayor. El elemento mayor se encuentra
montando un montículo que permitirá volver a encontrar rápidamente en la siguiente iteración el nuevo mayor
39ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Heapsort: algoritmo de ordenación (II)
A = Heapsort (A, N) % Algoritmo de ordenación basado en el montículo
A = ConstruyeMonticuloInicial (A, N); % inicialmente todo desordenado
Tam_Mont = N;
1 For i= N to 2, step –1 % los elementos mayores se criban a la izquierda
x = A[1]; A[1] =A[i]; A[i] = x; % Intercambia A[1] con A[i]
Tam_Mont = Tam_Mont - 1;
A = Monticuliza (A, Tam_Mont, 1); % cribar desde la raíz
end 1
Fin
Tam_Mont
40ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Heapsort: algoritmo de ordenación (II)
https://www.youtube.com/watch?v=EreoMaOBTzE
41ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Heapsort: algoritmo de ordenación (ejemplo)
25
131512
16 14 19 11
2018
1
2 3
4 5 6 7
8 9 10
1512
16 14 11
20
18
1
2 3
4 5 6 7
8 9
CONSTRUYE_MONTICULO:
19
13
25i
12
16 14 11
20
18
1
2 3
4 5 6 7
8
19
13
25i
15
14 11
20
181
2 3
4 5 6 7
13
25i
1516
12
19
11
20
18
1
2 3
4 5 6
13
25
i15
16
12
19
14
11
20
18
1
2 3
4 513
25
i
15
1612
19
14
11
20
18
1
2 3
413
25
i
15 16
12
19
14
20
18
2 313
25
i
15 16
12
19
14
1
11
20
18
2
13
25
i
15 16
12
19
14
1
11
20
18
13
25
i
15 16
12
19
14
1
11
ya ordenado
(a) (b)
(d)
(c)
(e) (f)
(g) (h) (i)
25
131512
16 14 19 11
2018
1
2 3
4 5 6 7
8 9 10
1512
16 14 11
20
18
1
2 3
4 5 6 7
8 9
CONSTRUYE_MONTICULO:
19
13
25i
12
16 14 11
20
18
1
2 3
4 5 6 7
8
19
13
25i
15
14 11
20
181
2 3
4 5 6 7
13
25i
1516
12
19
11
20
18
1
2 3
4 5 6
13
25
i15
16
12
19
14
11
20
18
1
2 3
4 513
25
i
15
1612
19
14
11
20
18
1
2 3
413
25
i
15 16
12
19
14
20
18
2 313
25
i
15 16
12
19
14
1
11
20
18
2
13
25
i
15 16
12
19
14
1
11
20
18
13
25
i
15 16
12
19
14
1
11
ya ordenado
(a) (b)
(d)
(c)
(e) (f)
(g) (h) (i)
Datos iniciales
42ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Quicksort (Ordenación rápida)
• Mejora de Intercambio directo
– Se basa en hacer muchos intercambios de
elementos consecutivos
– Quicksort: intercambios sobre distancias LARGAS
- +
Intercambio
Intercambio directo
- +
Método rápido
Inventor: A. Hoare, en 1962
43ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Quicksort
• Idea:
– Desacoplar la solución en dos problemas independientes,
solucionables por separado (paradigma divide y vencerás)
– Punto clave: Cómo dividir rápidamente
dividir
N pequeño
Solución
Solucionar
Solucionar
Solucionar
dividir
Solucionar Solucionar
Ojo, no hay proceso de mezcla para unir las soluciones (como en
Mezcla Directa)
44ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Quicksort: Criterio de división
8521 91 43d
Ejemplo:
• El array A[iz ... de] se divide (reordena) en dos más pequeños A[iz ... d]
y A[d+1 ... de], en donde se cumple que:
– Cada elemento de A[iz ... d] es MENOR o IGUAL que cada elemento de
A[d+1 ... de]deiz d
iz d d+1 de
El índice d se determina durante el proceso de división a partir de un
valor umbral o "pivote"
45ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Quicksort: Divide
de
iz
i
j
A[i]< umbral
A[j]> umbral
[A, j] = Divide (A, iz, de) % devuelve el array reorganizado y la posición de corte d
[A, umbral] = SeleccionaUmbral (A, iz, de); % Además pone el pivote en A[iz]
i = iz ; j = de; % inicializa contadores
CONTINUAR = 1;
1 while (CONTINUAR = 1)
while (A[i] < umbral) i = i+1; end; % avanza a la derecha
while (umbral < A[j]) j = j- 1; end; % avanza a la izquierda
2 if (i<j) then
intercambiar A[i] con A[j];
i=i+1; j=j-1; % para salir while 1
else
CONTINUAR = 0; % j tiene la posición de corte
end 2
end 1
Fin
NOTA: Para que funcione el pivote tiene que estar en A[iz]
46ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Quicksort: Ejemplo división
85 21 9 143
umbral= 5
i j
8521 91 43i j
8521 91 43i j
8521 91 43i j
8521 91 43ij
STOP
d
[A, j] = Divide (A, iz, de)
[A, umbral] = SeleccionaUmbral (A, iz, de)
i = iz ; j = de;
CONTINUAR = 1;
1 while (CONTINUAR = 1)
while (A[i] < umbral) i = i+1; end;
while (umbral < A[j]) j = j- 1; end;
2 if (i<j) then
intercambiar A[i] con A[j];
i=i+1; j=j-1;
else
CONTINUAR = 0;
end 2
end 1
Fin
47ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Quicksort: Algoritmo de ordenación
A = Quicksort (A, iz, de) % iz y de indican la zona del array A a ordenar
1 if (iz < de) then % ya está resuelto si sólo hay un elemento
[A, d] = Divide (A, iz, de); % divide y reordena (modifica A)
A = Quicksort (A, iz, d); % repite recursivamente lado izquierdo
A = Quicksort (A, d+1, de); % repite recursivamente lado derecho
end 1
Fin
A={ }de=Niz=1 d
1 d d+1 N
48ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Quicksort: Selección del umbral (I)
• Lo más sencillo:
– Hay un caso claramente malo ¿cuál es?
• Lo deseable, pero demasiado “costoso”:
– Utilizar la mediana para asegurar una división balanceada
[A, u] = SeleccionaUmbral (A, iz, de) % iz y de indican la zona a considerar
u = A[iz]; % simplemente coge la clave del primer elemento (iz) como umbral
% también se podría coger el del final (es la misma idea)
Fin
[A, u] = SeleccionaUmbral (A, iz, de) % iz y de indican la zona a considerar
m = CalculaMediana (A, iz, de); % A[m] = la mediana de A[iz ... de]
intercambiar A[iz] con A[m];
u = A[iz]; % asegura que el umbral está en iz
Fin
49ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Counting sort: Planteamiento
• Suposición:
– Todas las claves son enteros en el rango 1-k, para algún
entero k
• Idea:
– determinar para cada elementos cuántos tienen menor clave que él y,
– utilizar dicho valor para determinar la posición en el array ordenado
– Con cuidado para no poner varios elementos en la mismo sitio ...
A={ }N1
B={ }N1
Hay 7 items con A[]<A[3] Insertar en B[8]
50ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Counting sort: Algoritmo
1 k=4
C={ }2
21 N=8
A={ }
N=8
B={ }2
4
B = CountingSort (A, B, N, k) % el resultado en B, tiene que tener tamaño N
Crear array e inicializar C[1...k]=Ø; % array auxiliar de tamaño k1 For j=1 to N % C[i] contiene número items iguales a i
C[ A[j] ] = C[ A[j] ] +1 ;end 12 For i=2 to k % C[i] contiene número items ≤ que i
C[i] = C[i] +C[i-1] ;end 23 For j= N to 1, step -1
B[ C[A[j]] ]= A[j];C[A[j]] = C[A[j]] -1; % ojo claves repetidas
end 3Fin
51ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Counting sort: Ejemplo
31 143 6 4 41 N=8
A={ }
03 12 0 21 k=6
C={ }2 3 4 5
7 82 41 k=6
C={ }2 3 4 5
For 1:
For 2: 2 7
7 82 41 k=6
C={ }2 3 4 5
For 3:
2 7
41 N=8
B={ }
31 143 6 4 41 N=8
A={ }
7
B = CountingSort (A, B, N, k)Crear array e inicializar C[1...k]=Ø;1 For j=1 to N
C[ A[j] ] = C[ A[j] ] +1 ;end 12 For i=2 to k
C[i] = C[i] +C[i-1] ;end 23 For j= N to 1, step -1
B[ C[A[j]] ]= A[j];C[A[j]] = C[A[j]] -1;
end 3Fin
52ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Radix sort
• Creado en los años 30 para ordenar las tarjetas perforadas
utilizadas en los ordenadores, ya sólo en museos
(programado mecánicamente)
• Util para ordenar información por múltiples campos:
– Fechas (año/mes/día) Personas (apellidos)
• Ordenar N items en donde la clave es
– clave_a_utilizar = digito1, digito2, digito3, ..., digitod
– - significativo a +significativo
• Formas de hacerlo:
– Utilizar un algoritmo en donde las comparaciones son
jerárquicas
– Ordenar la información d veces con un algoritmo estable, cada
vez en un dígito diferente
53ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Radix sort: Algoritmo
• Idea básica:
– Ordenar primero por el dígito menos significativo
A = RadixSort (A, N, d)1 For c=1 to d % se hacen d ordenaciones, una para cada ´”dígito”
A = AlgoritmoOrdEstable(A, N) utilizando clave ordenación c;end 1Fin
32 9 72 0 72 0 32 9 45 7 35 5 32 9 35 5 65 7 43 6 43 6 43 6 83 9 45 7 83 9 45 7 43 6 65 7 35 5 65 7 72 0 32 9 45 7 72 0 35 5 83 9 65 7 83 9
• Es importante identificar quién tiene
que ser el dígito menos significativo ...
• Si los dígitos son valores enteros en el
rango 1-k, y k no es muy grande
• AlgoritmoOrdEstable = CountingSort
54ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Radix sort: Ejemplo mala utilización
Así no está
ordenado por
fechas (aunque el
algoritmo sea
estable)
d m aOrdenar por fechas los siguientes elementos utilizando como
clave de ordenación
clave_a_utilizar = dd, mm, aaaa
(primero ordenamos por año, luego por mes,
y finalmente por día)
¿?
55ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Radix sort: Ejemplo bueno
Así SÍ está
ordenado por
fechas
a m dOrdenar por fechas los siguientes elementos utilizando como
clave de ordenación
clave_a_utilizar = aaaa, mm, dd
(primero ordenamos por día, luego por mes,
y finalmente por año)
56ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Bucket sort (I)
• Suposición:
– Las claves que aparecen en el array a ordenar, son valores
entre [0,1) y están "bastante bien repartidas“
[0
...
1
)
Histograma Array a ordenar
57ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Bucket sort (II)
• Cuantos más datos a ordenar tengamos, más eviente será
dicha suposición:
300 datos
10 datos
IDEAL: Las claves son generadas por proceso “aleatorio” que distribuye las claves uniformemente en [0,1)
58ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Bucket sort: Algoritmo (I)
• Supuesto que los valores de las claves están bien
repartidos:
• Se puede dividir el intervalo [0,1) en N subintervalos de
igual tamaño, llamados "buckets“ o “recipientes”
• Distribuir los N elementos en los recipientes
• No se sabe cuantos elementos irán a cada recipiente, pero no
serán muchos...
• Ordenar los elementos de cada recipiente utilizando
Inserción Directa (será un número pequeño)
• Juntar todos los elementos de los recipientes
59ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Bucket sort: Algoritmo (II)
• Ejemplo (array con 10 elementos):
– A = [0.995 0.075 0.873 0.757 0.901 0.915 0.515 0.055 0.262 0.386];
Recipientes
1.0
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0.0
60ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Bucket sort: Algoritmo (III)
• El conjunto de recipientes se modela como un vector de
listas enlazadas
– B[0...N-1]: array auxiliar de listas enlazadas
B = BucketSort (A, N, k) % 0≤A[i]<1 , i=1:N
Crear array aux B[0...N-1]; % crea array auxiliar
1 For i=1 to N % guarda en los recipientesinsertar A[i] en lista B[floor(N*A[i])];
end 1
2 For i=0 to N-1 % ordena cada recipienteOrdenar lista B[i] con InsercionDirecta;
end 2
Concatenar listas B[0], B[1], ... , B[N-1] ;
Fin
61ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Bucket sort: Algoritmo (IV)
• Para ordenar el array:
– A = [0.995 0.075 0.873 0.757 0.901 0.915 0.515 0.055 0.262 0.386];
0.995 0.075 0.873 0.757 0.901 0.915 0.515 0.055 0.262 0.386
A B
0 1 2 3 4 5 6 7 8 9 0.995
0.075
0.8730.757
0.901 0.915
0.515
0.2620.386
0.055
62ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA
Comparativa tiempos de ejecución
top related