ALGORITMICA PARTE II: Algoritmos existentes 3... · 2019-10-01 · 5 ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA Algoritmos de ordenación externa (I) • La información a ordenar no

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


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


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


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


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


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


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


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


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


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


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


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


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


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


Selección directa (I)

• Idea


Búsqueda


Búsqueda Insertar en el siguiente

Seleccionar el siguiente

Inserción directa

Selección d irecta


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


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


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


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


Mezcla directa (III)

• Ejemplo


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


Intercambio directo: burbuja (I)

A={ }Secuencia or igendestino


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


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


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


iz

j

- + +-

destino(ya ordenado)

de

k

iz'

A={ }origendestino

(ya ordenado)

iz

j

- + +-

destino(ya ordenado)

de

[iz ... de]

Alternancia


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


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í:


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“


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


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


Heapsort


Insertar en el siguiente


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"


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):


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


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

-

+


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


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


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


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


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


Heapsort: algoritmo de ordenación (II)

https://www.youtube.com/watch?v=EreoMaOBTzE


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


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


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)


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"


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]


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


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


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


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]


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


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


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


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


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)

¿?


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)


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


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)


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


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


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


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


Comparativa tiempos de ejecución

Documents

ALGORITMICA PARTE II: Algoritmos existentes 3... · 2019-10-01 · 5 ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA Algoritmos de ordenación externa (I) • La información a ordenar no