Ordenación por selección
Características.
•
Su tiempo de ejecución es O(N2) para el mejor, peor y caso promedio.
•
Es el más fácil de codificar de los mostrados en este documento.
•
Si el array de datos es A y su tamaño es N, lo que hace el algoritmo, para cada i de
[0..N-2] es intercambiar A[i] con el mínimo elemento del subarray [A[i+1], ...,
A[N]].
•
Dado que es muy simple de codificar, aunque no tiene los mejores tiempos de
ejecución, es apropiado utilizarlo para arrays de datos relativamente pequeños.
void
intercambiar (Dato * A, int i, int j)
{
Dato tmp = A[i];
A[i] = A[j];
A[j] = tmp;
}
void
ordenacion_seleccion (Dato * A, int N)
{
int i, j, k;
for (i = 0; i < N - 1; i++)
{
for (k = i, j = i + 1; j < N; j++)
Algoritmos de ordenación
if (A[j] < A[k])
k = j;
if (k != i)
intercambiar (A, i, k);
}
}
Ordenación por inserción
Características.
•
Es un algoritmo sencillo de entender y de codificar.
•
Si el tamaño de la entrada es N, entonces el orden del tiempo de ejecución, para el
peor caso es O(N
2);
•
Si la entrada esta "casi ordenada", el algoritmo se ejecuta mucho más rápidamente.
Esta velocidad tiende a un tiempo O(N), peor caso que se cumple cuando la entrada
está totalmente ordenada.
•
Es por la propiedad anterior que este algoritmo, a pesar de no ser el más rápido para
entradas grandes, suele usarse de la siguiente manera: Se semi ordena la entrada con
algún otro algoritmo más rápido y más adecuado para entradas grandes. Luego,
cuando tenemos la entrada "casi ordenada" usamos este algoritmo. La velocidad de
ejecución será muy buena por dos razones: su tiempo de ejecución tiende a O(N) con
entradas "casi ordenadas" (lo cual es un tiempo excelente), y la simpleza de su
implementación hará que se ejecute más rápido que otros algoritmos más complejos.
Esto se implementará en Section 8.
Explicación del algoritmo.
Sea A el array a ordenar con N elementos. El algoritmo
consiste en recorrer todo el array A comenzando desde la posición p=2 y terminando en
p=N. Para cada p, se trata de ubicar en el lugar correcto el elemento A[p] en entre los
elementos anteriores: A[p-1], A[p-2], ..., A[0].
Dada la posición actual p, el algoritmo se basa en que los elementos A[0], A[1], ...,
A[p-1] ya están ordenados.
void
ordenacion_insercion (Dato * A, int N)
{
int p, j;
Algoritmos de ordenación
Dato tmp;
for (p = 1; p < N; p++)
{
tmp = A[p];
j = p - 1;
while ((j >= 0) && (tmp < A[j]))
{
A[j + 1] = A[j];
j--;
}
A[j + 1] = tmp;
}
}
Establezcamos la siguiente definición para poder discutir sobre el orden del tiempo de
ejecución del algoritmo y algunas de sus características.
Inversión.
Si hablamos de orden creciente, decimos que en un array A de n datos, la
pareja
(A[i],A[j]) es una inversión si se cumple que i<j y A[i]>A[j]. (en orden
decreciente sería el caso contrario).
Es decir, una
inversión es aquella pareja (A[i],A[j]) que rompe con el orden de una
secuencia de datos. Dada una secuencia A, si pudiéramos detectar todas sus inversiones
e intercambiar los valores de las mismas obtendríamos la secuencia ordenada. Por
ejemplo, considérese la secuencia
(5 3 9 7). Las inversiones de esta secuencia son
(5,3) y (9,7). Intercambiando el 5 por el 3 y el 9 por el 7 obtenemos la secuencia
ordenada
(3 5 7 9).
El algoritmo de ordenación por inserción lo que hace es recorrer todo el array
detectando inversiones (la segunda condición del
while()) y corrigiéndolas (una por
una en cada iteracción del
while()). Dado que existe esta relación entre el algoritmo
de ordenación y el número de inversiones, calculando el número medio de inversiones
en la secuencia de datos se pueden obtener cotas precisas sobre el tiempo de ejecución
del algoritmo.
Puede demostrarse fácilmente que le número medio de inversiones en un array de n
elementos es n(n-1)/4 = O(n
2).
Podemos decir entonces que el algoritmo de ordenación por inserción (y en realidad
cualquier algoritmo de ordenación que intercambie sólo elementos adyacentes),
requiere un tiempo de hasta orden n
2 en promedio.
Ordenación de Shell (ShellSort)
1
Características.
•
A diferencia del algoritmo de ordenación por inserción, este algoritmo intercambia
elementos distantes. Es por esto que puede deshacer más de una inversión en cada
intercambio, hecho del cual nos aprovechamos para ganar velocidad.
•
La velocidad del algoritmo dependerá de una secuencia de valores (llamados
incrementos, de los cuales hablaremos más abajo) con los cuales trabaja
utilizándolos como distancias entre elementos a intercambiar. Veremos que con
algunas secuencias podremos obtener ordenes de tiempo de ejecución en el peor caso
de O(n
2), O(n^(3/2)) y O(n^(4/3)).
•
Se considera la ordenación de Shell como el algoritmo más adecuado para ordenar
entradas de datos moderadamente grandes (decenas de millares de elementos) ya que
su velocidad, si bien no es la mejor de todos los algoritmos, es aceptable en la
práctica y su implementación (código) es relativamente sencillo.
Antes que nada definiremos el concepto de k-ordenación.
Secuencia k-ordenada.
Decimos que una secuencia A de n elementos está k-ordenada
(siendo k un natural) si, para todo i de [0,n] se cumple que los elementos A[i + hk]
están ordenados, siendo h un entero y siempre que el índice i+hk esté en [0,n].
El algoritmo de ordenación de Shell lo que hace en realidad es tomar una secuencia de
incrementos h
1, h2, ..., hp y en la etapa k-esima realizar una hk-ordenación de los datos.
La única condición que debe respetar la secuencia de incrementos es h
p=1 de modo tal
que en la última etapa se hace una 1-ordenación (o sea una ordenación normal).
¿Cómo hacemos para k-ordenar un array A de n elementos?
Dado que la
ordenación por inserción lo que hace es una 1-ordenación, usaremos el mismo
algoritmo para k-ordenar, pero comparando sólo elementos k-distanciados. Más
detalladamente, para cada i de [k+1, n] intercambiamos (si hay que hacerlo) A[i] con
alguno de los elementos anteriores a i con distancia múltiplo de k (es decir,
intercambiamos A[i] con con alguno de los elementos A[i-k], A[i-2k], ...).
Una propiedad importante de implementar una k-ordenación de este modo es que si
k>p entonces realizar una p-ordenación luego de una k-ordenación conserva el k-orden.
El lector podría estar preguntándose por qué k-ordenar varias veces si al final
terminamos haciendo una 1-ordenación utilizando ordenación por inserción. ¿Por qué
no hacer simplemente una 1-ordenación? Recordemos que la ordenación por inserción
6
Algoritmos de ordenación
trabaja mucho más rápido si la secuencia de datos está "casi ordenada". Así, luego de
efectuar varias k-ordenaciones, en la última etapa, la 1-ordenación tiene un array "casi
ordenado", por lo que el algoritmo se ejecuta más rápidamente.
Podemos decir entonces que la ordenación de Shell, es en realidad una ordenación por
inserción pero a la cual se le pasa el array "casi ordenado". Esta "casi ordenación" se
efectúa mediante h
k-ordenaciones para algunos hk.
Como el lector podrá intuir, la velocidad del algoritmo dependerá de esta secuencia de
incrementos h
k y una buena secuencia de incrementos constará de naturales primos
relativos entre sí.
Secuencias de incrementos usadas comúnmente.
•
La propuesta por Shell: n/2, n/4, ..., n/(2k), ..., 1. Ventajas: es fácil de calcular.
Desventajas: no optimiza mucho la velocidad del algoritmo puesto que los
incrementos tienen factores comunes (no son primos relativos). El tiempo de
ejecución promedio con esta secuencia de incrementos será O(n
2).
•
La propuesta por Hibbard: 2k-1, ..., 7, 3, 1; donde k se elije de modo tal que 2k-1 < n/2
y 2
k+1-1 > n/2. Aunque no se ha podido demostrar formalmente (sólo por medio de
simulaciones), utilizar esta secuencia de incrementos hace que el algoritmo de Shell
tenga un tiempo de ejecución promedio O(n
5/4). Una cota para el peor caso (que se
puede demostrar utilizando la teoría de números y combinatoria avanzada) es O(n
3/2).
•
La propuesta por Sedgewick: 4k-3·2k+1, ..., 19, 5, 1; con la cual se pueden obtener
tiempos de ejecución O(n
4/3) para el peor caso y O(n7/6) para el caso promedio.
A continuación damos el algoritmo formal de la ordenación de Shell, en el cual
utilizaremos los incrementos propuestos por Shell por simplicidad en el código:
void
ordenacion_shell (Dato * A, int N)
{
int incr = N / 2, p, j;
Dato tmp;
do
{
for (p = incr + 1; p < N; p++)
{
tmp = A[p];
j = p - incr;
while ((j >= 0) && (tmp < A[j]))
{
A[j + incr] = A[j];
7
Algoritmos de ordenación
j -= incr;
}
A[j + incr] = tmp;
}
incr /= 2;
}
while (incr > 0);
}
Observar que dentro del
do { ... } while(), el algoritmo es análogo a la
ordenación por inserción, salvo que se compara
tmp con los elementos anteriores
incr
-distanciados.
Ordenación por montículos (Heapsort)
Características.
•
Es un algoritmo que se construye utilizando las propiedades de los montículos
binarios.
•
El orden de ejecución para el peor caso es O(N·log(N)), siendo N el tamaño de la
entrada.
•
Aunque teóricamente es más rápido que los algoritmos de ordenación vistos hasta
aquí, en la práctica es más lento que el algoritmo de ordenación de Shell utilizando
la secuencia de incrementos de Sedgewick.
Breve repaso de las propiedades de los montículos
binarios (heaps)
Recordemos que un montículo Max es un árbol binario completo cuyos elementos están
ordenados del siguiente modo: para cada subárbol se cumple que la raíz es mayor que
ambos hijos. Si el montículo fuera Min, la raíz de cada subárbol tiene que cumplir con ser
menor que sus hijos.
Recordamos que, si bien un montículo se define como un árbol, para representar éste se
utiliza un array de datos, en el que se acceden a padres e hijos utilizando las siguientes
transformaciones sobre sus índices. Si el montículo está almacenado en el array A, el padre
de A[i] es A[i/2] (truncando hacia abajo), el hijo izquierdo de A[i] es A[2*i] y el hijo
derecho de A[i] es A[2*i+1].
8
Algoritmos de ordenación
Al insertar o eliminar elementos de un montículo, hay que cuidar de no destruir la
propiedad de orden del montículo. Lo que se hace generalmente es construir rutinas de
filtrado (que pueden ser ascendentes o descendentes) que tomen un elemento del montículo
(el elemento que viola la propiedad de orden) y lo muevan vérticalmente por el árbol hasta
encontrar una posición en la cual se respete el orden entre los elementos del montículo.
Tanto la inserción como la eliminación (
eliminar_min o eliminar_max según sea un
montículo Min o Max respectivamente), de un elemento en un montículo se realizan en un
tiempo O(log(N)), peor caso (y esto se debe al orden entre sus elementos y a la
característica de árbol binario completo).
Estrategia general del algoritmo.
A grandes razgos el algoritmo de ordenación por
montículos consiste en meter todos los elementos del array de datos en un montículo
MAX, y luego realizar N veces
eliminar_max(). De este modo, la secuencia de
elementos eliminados nos será entregada en ordes decreciente.
Implementación práctica del algoritmo.
Existen dos razones por las que la estrategia
general debe ser refinada: el uso de un tad auxiliar (montículo binario) lo cual podría
implicar demasiado código para un simple algoritmo de ordenación, y la necesidad de
memoria adicional para el montículo y para una posible copia del array. Estas cosas
también implican un gasto en velocidad.
Lo que se hace es reducir el código al máximo reduciéndose lo más posible la
abstracción a un montículo. Primero que nada, dado el array de datos, este no es
copiado a un montículo (insertando cada elemento). Lo que se hace es, a cada elemento
de la mitad superior del array (posiciones 0,1,...,N/2) se le aplica un filtrado
descendente (se "baja" el elemento por el árbol binario hasta que tenga dos hijos que
cumplan con el orden del montículo. Esto bastará para hacer que el array cumpla con
ser un montíclo binario.
Notamos también que al hacer un eliminar_max() se elimina el primer elemento del
array, se libera un lugar a lo último de este. Podemos usar esto para no tener que hacer
una copia del array para meter las eliminaciónes sucesivas. Lo que hacemos es meter la
salida de eliminar_max() luego del último elemento del montículo. Esto hace que luego
de N-1 eliminar_max(), el array quede ordenado de menor a mayor.
Para ahorrar código queremos lograr insertar y eliminar_max() con una sola rutina de
filtrado descendente. Ya explicamos cómo hacer que el array de datos A preserve el
orden de los elementos de un montículo. Lo que hacemos para ordenarlo usando sólo la
rutina de filtrado descendente es un eliminar_max() intercambiando el primer elemento
del array por el último del montículo y filtrar el nuevo primer elemento hasta que se
respete el orden Max. Quizá esto quede más claro mirando el código.
9
Algoritmos de ordenación
void
filtrado_desc (Dato * A, int i, int N)
{
/* queremos que se respete el orden MAX del montículo */
Dato tmp = A[i];
int hijo = 2 * i;
if ((hijo < N) && (A[hijo + 1] > A[hijo]))
hijo++;
while ((hijo <= N) && (tmp < A[hijo]))
{
/* elijo bien el hijo */
if ((hijo < N) && (A[hijo + 1] > A[hijo]))
hijo++;
A[i] = A[hijo];
i = hijo;
hijo = 2 * i;
}
A[i] = tmp;
}
void
intercambiar (Dato * A, int i, int j)
{
Dato tmp = A[i];
A[i] = A[j];
A[j] = tmp;
}
void
heapsort (Dato * A, int N)
{
int i;
/* meto los datos en el montículo (ordeno) */
for (i = N / 2; i >= 0; i--)
filtrado_desc (A, i, N);
/* saco los datos y los meto al final para obtener el array ordenado */
for (i = N - 1; i > 0; i--)
{
10
Algoritmos de ordenación
intercambiar (A, 0, i);
filtrado_desc (A, 0, i - 1);
}
}
Ordenación por Intercalación (mergesort)
Características.
•
Es un algoritmo recursivo con un número de comparaciones mínimo. El tiempo de
ejecución promedio es O(N log(N)).
•
Su desventaja es que trabaja sobre un array auxiliar lo cual tiene dos consecuencias:
uso de memoria extra y trabajo extra consumido en las copias entre arreglos (aunque
es un trabajo de tiempo lineal).
•
Es una aplicación clásica de la estrategia para resolución de algoritmos "divide y
vencerás". Esta estrategia plantea el hecho de que un problema puede ser dividido en
varios subproblemas y una vez resueltos estos se puede proceder a unir las
soluciones para formar la solución del problema general. La solución de los
subproblemas más pequeños se realiza de la misma manera: es decir, se van
resolviendo problemas cada vez más pequeños (hasta encontrarnos con un caso base:
problema no divisible con solución tribial).
En cada recursión se toma un array de elementos desordenados. Se lo divide en dos
mitades, se aplica la recursión en cada una de estas y luego (dado que al finalizar estas
recursiones tenemos las dos mitades ordenadas) se
intercalan ambas para obtener el
array ordenado.
Intercalar.
Es la operación que le da el nombre a este algoritmo. La intercalación toma
dos secuencias (arrays) de elementos y a partir de estas construye una tercera secuencia
que contiene todos los elementos de estas en orden.
Implementación de la intercalación.
Sean dos arrays ordenados A y B (cuyas
longitudes pueden ser distintas). Sea el array C tal que |C|>=|A|+|B| (tiene capacidad
para almacenar todos los elementos de ambas listas A y B). Sean los contadores ap, bp
y cp con valor inicial 0 (se ponen al inicio de sus arreglos respectivos). Lo que hace
intercalar
es copiar el menor de A[ap] y B[bp] en C[cp] y avanzar los contadores
apropiados. Cuando se agota cualquier lista de entrada (A o B), los datos que quedan en
la otra lista se copian en C.
11
Algoritmos de ordenación
Esperamos que al leer el código, el lector entienda los detalles menores tanto de la
rutina recursiva del algoritmo de recursión como de la rutina
intercala().
void ord_intercalacion (Dato * A, Dato * tmp, int izq, int der);
/* Función recursiva! A es el array de datos. tmp debe ser un
array de tamaño mayor o igual a A. izq y der son los extremos
del subarreglo sobre el cual trabajaremos en esta
recursión. */
void intercalar (Dato * A, Dato * tmp, int izq, int centro, int der);
/* lo que hace esta rutina es intercalar las particiones
[A[izq], ..., A[centro-1] ] y [ A[centro], ..., A[der] ]
(que deberían estar ya ordenadas) en el subarray
[ tmp[izq], ..., tmp[der] ] y luego copiar los elementos
nuevamente a A, en el subarray [ A[izq], ..., A[der] ] */
void
mergesort (Dato * A, int N)
{
Dato *tmp = crear (N); /* creamos un array auxiliar del mismo
tamaño que A */
ord_intercalacion (A, tmp, 0, N - 1);
}
void
ord_intercalacion (Dato * A, Dato * tmp, int izq, int der)
{
if (izq < der)
/* este if comprueba el caso base que es cuando la partición
pasada no tiene elementos. */
{
/* dividimos a la mitad el subarray [A[izq],...,A[der]] */
int centro = (izq + der) / 2;
/* aplicamos la recursión en ambas mitades */
ord_intercalacion (A, tmp, izq, centro);
ord_intercalacion (A, tmp, centro + 1, der);
/* a este punto ambas mitades deberían estar ordenadas por
lo que las intercalamos para unirlas en una sola
secuencia ordenada. */
12
Algoritmos de ordenación
intercalar (A, tmp, izq, centro + 1, der);
}
}
void
intercalar (Dato * A, Dato * tmp, int izq, int centro, int der)
{
/* mis particiones serán [izq,...,centro-1] y
[centro,...,der] */
/* contadores para la primera mitad, la segunda y para la
intercalacion respectivamente. */
int ap = izq, bp = centro, cp = izq;
while ((ap < centro) && (bp <= der))
{
if (A[ap] <= A[bp])
{
tmp[cp] = A[ap];
ap++;
}
else
{
tmp[cp] = A[bp];
bp++;
}
cp++;
}
/* terminamos de intercalar, ahora metemos los elementos
restantes de la lista que aún no ha terminado de ser
procesada. */
while (ap < centro)
{
tmp[cp] = A[ap];
cp++;
ap++;
}
while (bp <= der)
{
tmp[cp] = A[bp];
cp++;
bp++;
13
Algoritmos de ordenación
}
/* ahora que tenemos la intercalación finalizada en tmp, la
pasamos a A */
for (ap = izq; ap <= der; ap++)
A[ap] = tmp[ap];
}
Observar como la función principal
mergesort() solamente es un manejador de la
función
ord_intercalacion() en la cual se realiza todo el trabajo recursivamente.
Si bien el algoritmo puede parecer largo, es más fácil (desde nuestro punto de vista)
entenderlo que otros algoritmos más cortos pero más complejos como por ejemplo la
ordenación de shell. La única parte difícil es entender cómo funciona la recursión ya
que el algoritmo intercalar es bastante fácil.
Ordenación rápida (quicksort)
Características.
•
Es el algoritmo de ordenación más rápido (en la práctica) conocido. Su tiempo de
ejecución promedio es O(N log(N)).
•
Para el peor caso tiene un tiempo O(N2), pero si se codifica correctamente las
situaciones en las que sucede el peor caso pueden hacerse altamente improbables.
•
EN la práctica, el hecho de que sea más rápido que los demás algoritmos de
ordenación con el mismo tiempo promedio O(N log(N)) está dado por un ciclo
interno muy ajustado (pocas operaciones).
•
Al igual que el algoritmo de ordenación por intercalación, el algoritmo de
ordenación rápida es fruto de la técnica de resolución de algoritmos "divide y
vencerás". Como ya se explicó, la técnica de divide y vencerás se basa en, en cada
recursión, dividir el problema en subproblemas más pequeños, resolverlos cada uno
por separado (aplicando la misma técnica) y unir las soluciones.
Se explica a continuación, a grandes razgos, qué se hace en cada recursión:
1. Si el array de datos es vacío o tiene un sólo elemento no hacemos nada y salimos
de la recursión.
14
Algoritmos de ordenación
2. Elegimos un elemento
v (llamado pivote) del array de datos.
3. Particionamos el array de datos A en tres arrays:
•
A1={todos los elementos de A - {v} que sean menores o iguales que v}
•
A2={v}
Utilizando múltiples algoritmos
En Section 3 prometimos usar el algoritmo de ordenación por inserción para terminar
de ordenar un array de datos "casi ordenado". En esta sección examinaremos este caso
realizando lo siguiente: Modificamos ligeramente el algoritmo de ordenación rápida
para que ordene particiones de hasta CORTE elementos, donde CORTE es un entero
previamente determinado en función del tamaño de la entrada. Mostramos la
implementación esperando que se entienda el cometido de las ligeras modificaciones:
#include <math.h>
static int CORTE;
void ord_rapida (Dato * A, int izq, int der);
void
quicksort (Dato * A, int N)
{
CORTE=log(N)*log(N);
ord_rapida (A, 0, N - 1);
if(CORTE>1)
ordenacion_insercion(A, N);
}
void
ord_rapida (Dato * A, int izq, int der)
/* se trabaja en el subarray [A[izq],...,A[der]] */
{
if (der - izq > CORTE) /* caso base de la recursión */
{
{ /* elegimos el pivote y lo ponemos en A[der-1] */
int centro = div2 (izq + der);
if (A[izq] > A[centro])
intercambiar (A, izq, centro);
if (A[izq] > A[der])
intercambiar (A, izq, der);
if (A[centro] > A[der])
intercambiar (A, centro, der);
intercambiar (A, centro, der - 1);
}
{ /* "particionamos" */
int i = izq, j = der - 1;
Dato pivote = A[der - 1];
do
{
do
i++;
while (A[i] < pivote);
do
j--;
while (A[j] > pivote);
intercambiar (A, i, j);
}
while (j > i);
/* deshacemos el último intercambio el cual se efectuó
sin cumplirse i < j */
intercambiar (A, i, j);
/* ponemos el pivote en el medio de ambas particiones */
intercambiar (A, i, der - 1);
/* aplicamos la recursión en las particiones halladas */
ord_rapida (A, izq, i - 1);
ord_rapida (A, i + 1, der);
}
}
}
Como puede verse sólo se ha modificado una línea de la función
ord_rapida() pero
se ha modificado sustancialmente la función
quicksort(). En esta se determina el
valor correcto de la variable CORTE y se aplica, luego de ord_rapida() la función de
ordenación por inserción. Esta última se ejecutará muy rápido cuanto "mejor ordenado"
halla quedado el array de datos.
Hemos propuesto CORTE=log(N)
2 basados sólo en observaciones experimentales. Sin
•
A3={todos los elementos de A - {v} que sean mayores o iguales que v}
4. Aplicamos la recursión sobre A
1 y A3
2
5. Realizamos el último paso de "divide y vencerás" que es unir todas las soluciones
para que formen el array A ordenado. Dado que a este punto A
1 y A3 están ya
ordenados, concatenamos A
1, A2 y A3.
Si bien este algoritmo puede parecer sencillo, hay que implementar 2 y 3 de modo de
favorecer al máximo la velocidad del algoritmo. Es por esto que discutiremos a parte
cómo realizar estas tareas.
