El problema de ordenar un conjunto de datos (por ejemplo, en orden ascendente)
tiene gran importancia tanto teórica como práctica.
En esta sección veremos principalmente algoritmos que ordenan mediante
comparaciones entre llaves, para los cuales se puede demostrar una cota
inferior que coincide con la cota superior provista por varios algoritmos.
También veremos un algoritmo de otro tipo, que al no hacer comparaciones,
no está sujeto a esa cota inferior.
Cota inferior
Supongamos que deseamos ordenar tres datos A, B y C. La siguiente figura muestra un árbol de decisión posible para resolver este problema. Los nodos internos del árbol representan comparaciones y los nodos externos representan salidas emitidas por el programa.
Como se vio en el capítulo de búsqueda, todo árbol de decisión con H hojas tiene al menos altura log2 H, y la altura del árbol de decisión es igual al número de comparaciones que se efectúan en el peor caso.
En un árbol de decisión para ordenar n datos se tiene que H=n!, y por lo tanto se tiene que todo algoritmo que ordene n datos mediante comparaciones entre llaves debe hacer al menos log2 n! comparaciones en el peor caso.
Usando la aproximación de Stirling, se puede demostrar que log2 n! = n log2 n + O(n), por lo cual la cota inferior es de O(n log n).
Si suponemos que todas las posibles permutaciones resultantes son equiprobables, es posible demostrar que el número promedio de comparaciones que cualquier algoritmo debe hacer es también de O(n log n).
Este método fue inventado por C.A.R. Hoare a comienzos de los '60s, y sigue siendo el método más eficiente para uso general.
Quicksort es un ejemplo clásico de la aplicación del principio de dividir para reinar. Su estructura es la siguiente:
La recursividad termina, en principio, cuando se llega a sub-arreglos de tamaño cero o uno, los cuales trivialmente ya están ordenados. En la práctica veremos que es preferible detener la recursividad antes de eso, para no desperdiciar tiempo ordenando recursivamente arreglos pequeños, los cuales pueden ordenarse más eficientemente usando Ordenación por Inserción, por ejemplo.
Si suponemos, como una primera aproximación, que el pivote siempre resulta ser la mediana del conjunto, entonces el costo de ordenar está dado (aproximadamente) por la ecuación de recurrencia
T(n) = n + 2 T(n/2)
Esto tiene solución T(n) = n log2 n y es, en realidad, el mejor caso de Quicksort.
Para analizar el tiempo promedio que demora la ordenación mediante Quicksort, observemos que el funcionamiento de Quicksort puede graficarse mediante un árbol de partición:
Por la forma en que se construye, es fácil ver que el árbol de partición es un árbol de búsqueda binaria, y como el pivote es escogido al azar, entonces la raíz de cada subárbol puede ser cualquiera de los elementos del conjunto en forma equiprobable. En consecuencia, los árboles de partición y los árboles de búsqueda binaria tienen exactamente la misma distribución.
En el proceso de partición, cada elemento de los subárboles ha sido comparado contra la raíz (el pivote). Al terminar el proceso, cada elemento ha sido comparado contra todos sus ancestros. Si sumamos todas estas comparaciones, el resultado total es igual al largo de caminos internos.
Usando todas estas correspondencias, tenemos que, usando los resultados ya conocidos para árboles, el número promedio de comparaciones que realiza Quicksort es de:
Por lo tanto, Quicksort es del mismo orden que la cota inferior (en el caso esperado).
El peor caso de Quicksort se produce cuando el pivote resulta ser siempre el mínimo o el máximo del conjunto. En este caso la ecuación de recurrencia es
T(n) = n - 1 + T(n-1)
lo que tiene solución T(n) = O(n2). Desde el punto de vista del árbol de partición, esto corresponde a un árbol en "zig-zag".
Si bien este peor caso es extremadamente improbable si el pivote se escoge al azar, algunas implementaciones de Quicksort toman como pivote al primer elemento del arreglo (suponiendo que, al venir el arreglo al azar, entonces el primer elemento es tan aleatorio como cualquier otro). El problema es que si el conjunto viene en realidad ordenado, entonces caemos justo en el peor caso cuadrático.
Lo anterior refuerza la importancia de que el pivote se escoja al azar. Esto no aumenta significativamente el costo total, porque el número total de elecciones de pivote es O(n).
Quicksort puede ser optimizado de varias maneras, pero hay que ser muy cuidadoso con estas mejoras, porque es fácil que terminen empeorando el desempeño del algoritmo.
En primer lugar, es desaconsejable hacer cosas que aumenten la cantidad de trabajo que se hace dentro del "loop" de partición, porque este es el lugar en donde se concentra el costo O(n log n).
Algunas de las mejoras que han dado buen resultado son las siguientes:
Quicksort con "mediana de 3"
En esta variante, el pivote no se escoge como un elemento tomado al azar, sino que primero se extrae una muestra de 3 elementos, y entre ellos se escoge a la mediana de esa muestra como pivote.
Si la muestra se escoge tomando al primer elemento del arreglo, al del medio y al último, entonces lo que era el peor caso (arreglo ordenado) se transforma de inmediato en mejor caso.
De todas formas, es aconsejable que la muestra se escoja al azar, y en ese caso el análisis muestra que el costo esperado para ordenar n elementos es
(12/7) n ln n = 1.19 n log2 n
Esta reducción en el costo se debe a que el pivote es ahora una mejor aproximación a la mediana. De hecho, si en lugar de escoger una muestra de tamaño 3, lo hiciéramos con tamaños como 7, 9, etc., se lograría una reducción aún mayor, acercándonos cada vez más al óptimo, pero con rendimientos rápidamente decrecientes.
Uso de Ordenación por Inserción para ordenar sub-arreglos pequeños
Tal como se dijo antes, no es eficiente ordenar recursivamente sub-arreglos demasiado pequeños.
En lugar de esto, se puede establecer un tamaño mínimo M, de modo que los sub-arreglos de tamaño menor que esto se ordenan por inserción en lugar de por Quicksort.
Claramente debe haber un valor óptimo para M, porque si creciera indefinidamente se llegaría a un algoritmo cuadrático. Esto se puede analizar, y el óptimo es cercano a 10.
Como método de implementación, al detectarse un sub-arreglo de tamaño menor que M, se lo puede dejar simplemente sin ordenar, retornando de inmediato de la recursividad. Al final del proceso, se tiene un arreglo cuyos pivotes están en orden creciente, y encierran entre ellos a bloques de elementos desordenados, pero que ya están en el grupo correcto. Para completar la ordenación, entonces, basta con hacer una sola gran pasada de Ordenación por Inserción, la cual ahora no tiene costo O(n2), sino O(nM), porque ningún elemento esta a distancia mayor que M de su ubicación definitiva.
Ordenar recursivamente sólo el sub-arreglo más pequeño
Un problema potencial con Quicksort es la profundidad que puede llegar a tener el arreglo de recursividad. En el peor caso, ésta puede llegar a ser O(n).
Para evitar esto, vemos primero cómo se puede programar Quicksort en forma no recursiva, usando un stack. El esquema del algoritmo sería el siguiente (en seudo-Java):
void Quicksort(Object a[])
{
Pila S = new Pila();
S.apilar(1,N); // límites iniciales del arreglo
while(!S.estaVacia())
{
(i,j) = S.desapilar(); // sacar límites
if(j-i>0) // al menos dos elementos para ordenar
{
p = particionar(a,i,j); // pivote queda en a[p]
S.apilar(i,p-1);
S.apilar(p+1,j);
}
}
}
Con este enfoque se corre el riesgo de que la pila llegue a tener profundidad O(n). Para evitar esto, podemos colocar en la pila sólo los límites del sub-arreglo más pequeño, dejando el más grande para ordenarlo de inmediato, sin pasar por la pila:
void Quicksort(Object a[])
{
Pila S = new Pila();
S.apilar(1,N); // límites iniciales del arreglo
while(!S.estaVacia())
{
(i,j) = S.desapilar(); // sacar límites
while(j-i>0) // al menos dos elementos para ordenar
{
p = particionar(a,i,j); // pivote queda en a[p]
if(p-i>j-p) // mitad izquierda es mayor
{
S.apilar(p+1,j);
j=p-1;
}
else
{
S.apilar(i,p-1);
i=p+1;
}
}
}
}
Con este enfoque, cada intervalo apilado es a lo más de la mitad del tamaño del arreglo, de modo que si llamamos S(n) a la profundidad de la pila, tenemos:
S(n) <= 1 + S(n/2)
lo cual tiene solución log2 n, de modo que la profundidad de la pila nunca es más que logarítmica.
Es posible modificar el algoritmo de Quicksort para seleccionar el k-ésimo elemento de un arreglo. Básicamente, la idea es ejecutar Quicksort, pero en lugar de ordenar las dos mitades, hacerlo solo con aquella mitad en donde se encontraría el elemento buscado.
Suponemos que los elementos están en a[1],...,a[n] y que k está entre 1 y n. Cuando el algoritmo termina, el k-ésimo elemento se encuentra en a[k]. El resultado es el siguiente algoritmo, conocido como Quickselect, el cual se llama inicialmente como Quickselect(a,k,1,N).
void Quickselect(Object a[], int k, int i, int j)
{
if(j-i>0) // aún quedan al menos 2 elementos
{
p = particionar(a,i,j);
if(p==k) // ¡bingo!
return;
if(k<p) // seguimos buscando a la izquierda
Quickselect(a,k,i,p-1);
else
Quickselect(a,k,p+1,j);
}
}
Dado que en realidad se hace sólo una llamada recursiva y que ésta es del tipo "tail recursion", es fácil transformar esto en un algoritmo iterativo (hacerlo como ejercicio).
El análisis de Quickselect es difícil, pero se puede demostrar
que el costo esperado es O(n).
Sin embargo, el peor caso es O(n2).
Heapsort
A partir de cualquier implementación de una cola de prioridad es posible obtener un algoritmo de ordenación. El esquema del algoritmo es:
Si aplicamos esta idea a las dos implementaciones simples de colas de prioridad, utilizando lista enlazada ordenada y lista enlazada desordenada, se obtienen los algoritmos de ordenación por Inserción y por Selección, respectivamente. Ambos son algoritmos cuadráticos, pero es posible que una mejor implementación lleve a un algoritmo más rápido. En el capítulo de Tipos de Datos Abstractos se vió que una forma de obtener una implementación eficiente de colas de prioridad es utilizando una estructura de datos llamada heap.
Implementación de Heapsort
Al aplicar heaps en la implementación de cola de prioridad para construir un algoritmo de ordenación, se obtiene un algoritmo llamado Heapsort, para el cual resulta que tanto la fase de construcción de la cola de prioridad, como la fase de ordenación, tienen ambas costo O(n log n), de modo que el algoritmo completo tiene ese mismo costo.
Por lo tanto, Heapsort tiene un orden de magnitud que coincide con la cota inferior, esto es, es óptimo incluso en el peor caso. Nótese que esto no era así para Quicksort, el cual era óptimo en promedio, pero no en el peor caso.
De acuerdo a la descripción de esta familia de algoritmos, daría la impresión de que en la fase de construcción del heap se requeriría un arreglo aparte para el heap, distinto del arreglo de entrada. De la misma manera, se requeriría un arreglo de salida aparte, distinto del heap, para recibir los elementos a medida que van siendo extraídos en la fase de ordenación.
En la práctica, esto no es necesario y basta con un sólo arreglo: todas las operaciones pueden efectuarse directamente sobre el arreglo de entrada.
En primer lugar, en cualquier momento de la ejecución del algoritmo, los elementos se encuentran particionados entre aquellos que están ya o aún formando parte del heap, y aquellos que se encuentran aún en el conjunto de entrada, o ya se encuentran en el conjunto de salida, según sea la fase. Como ningún elemento puede estar en más de un conjunto a la vez, es claro que, en todo momento, en total nunca se necesita más de n casilleros de memoria, si la implementación se realiza bien.
En el caso de Heapsort, durante la fase de construcción del heap, podemos utilizar las celdas de la izquierda del arreglo para ir "armando" el heap. Las celdas necesarias para ello se las vamos "quitando" al conjunto de entrada, el cual va perdiendo elementos a medida que se insertan en el heap. Al concluir esta fase, todos los elementos han sido insertados, y el arreglo completo es un solo gran heap.
En la fase de ordenación, se van extrayendo elementos del heap, con lo cual este se contrae de tamaño y deja espacio libre al final, el cual puede ser justamente ocupado para ir almacenando los elementos a medida que van saliendo del heap (recordemos que van apareciendo en orden decreciente).
Optimización de la fase de construcción del heap
Como se ha señalado anteriormente, tanto la fase de construcción del heap como la de ordenación demoran tiempo O(n log n). Esto es el mínimo posible (en orden de magnitud), de modo que no es posible mejorarlo significativamente.
Sin embargo, es posible modificar la implementación de la fase de construcción del heap para que sea mucho más eficiente.
La idea es invertir el orden de las "mitades" del arreglo, haciendo que el "input" esté a la izquierda y el "heap" a la derecha.
En realidad, si el "heap" está a la derecha, entonces no es realmente un heap, porque no es un árbol completo (le falta la parte superior), pero sólo nos interesa que en ese sector del arreglo se cumplan las relaciones de orden entre a[k] y {a[2*k],a[2*k+1]}. En cada iteración, se toma el último elemento del "input" y se le "hunde" dentro del heap de acuerdo a su nivel de prioridad.
Al concluir, se llega igualmente a un heap completo, pero el proceso es significativamente más rápido.
La razón es que, al ser "hundido", un elemento paga un costo proporcional a su distancia al fondo del árbol. Dada las características de un árbol, la gran mayoría de los elementos están al fondo o muy cerca de él, por lo cual pagan un costo muy bajo. En un análisis aproximado, la mitad de los elementos pagan 0 (ya están al fondo), la cuarta parte paga 1, la octava parte paga 2, etc. Sumando todo esto, tenemos que el costo total está acotado por
lo cual es igual a n.
Radix sort
Los métodos anteriores operan mediante comparaciones de llaves, y están sujetos, por lo tanto, a la cota inferior O(n log n). Veremos a continuación un método que opera de una manera distinta, y logra ordenar el conjunto en tiempo lineal.
Supongamos que queremos ordenar n números, cada uno de ellos compuesto de k dígitos decimales. El siguiente es un ejemplo con n=10, k=5.
73895
93754
82149
99046
04853
94171
54963
70471
80564
66496
Imaginando que estos dígitos forman parte de una matriz, podemos decir que a[i,j] es el j-ésimo del i-ésimo elemento del conjunto.
Es fácil, en una pasada, ordenar el conjunto si la llave de ordenación es un solo dígito, por ejemplo el tercero de izquierda a derecha:
99046
82149
94171
70471
66496
80564
93754
73895
04853
54963
Llamemos j a la posición del dígito mediante el cual se ordena. La ordenación se puede hacer utilizando una cola de entrada, que contiene al conjunto a ordenar, y un arreglo de 10 colas de salida, subindicadas de 0 a 9. Los elementos se van sacando de la cola de entrada y se van encolando en la cola de salida Q[dj], donde dj es el j-ésimo dígito del elemento que se está transfiriendo.
Al terminar este proceso, los elementos están separados por dígito. Para completar la ordenación, basta concatenar las k colas de salida y formar nuevamente una sola cola con todos los elementos.
Este proceso se hace en una pasada sobre los datos, y toma tiempo O(n).
Para ordenar el conjunto por las llaves completas, repetimos el proceso dígito por dígito, en cada pasada separando los elementos según el valor del dígito respectivo, luego recolectándolos para formar una sola cola, y realimentando el proceso con esos mismos datos. El conjunto completo queda finalmente ordenado si los dígitos se van tomando de derecha a izquierda (¡esto no es obvio!).
Como hay que realizar k pasadas y cada una de ellas toma tiempo O(n), el tiempo total es O(k n), que es el tamaño del archivo de entrada (en bytes). Por lo tanto, la ordenación toma tiempo lineal en el tamaño de los datos.
El proceso anterior se puede generalizar para cualquier alfabeto, no sólo dígitos (por ejemplo, ASCII). Esto aumenta el número de colas de salida, pero no cambia sustancialmente el tiempo que demora el programa.
Archivos con records de largo variable
Si las líneas a ordenar no son todas del mismo largo, es posible alargarlas hasta completar el largo máximo, con lo cual el algoritmo anterior es aplicable. Pero si hay algunas pocas líneas desproporcionadamente largas y otras muy cortas, se puede perder mucha eficiencia.
Es posible, aunque no lo vamos a ver aquí, generalizar este algoritmo para
ordenar líneas de largo variable sin necesidad de alargarlas.
El resultado es que la ordenación se realiza en tiempo proporcional
al tamaño del archivo.
Mergesort y Ordenamiento Externo
Si tenemos dos archivos que ya están ordenados, podemos mezclarlos para formar un solo archivo ordenado en tiempo proporcional a la suma de los tamaños de los dos archivos.
Esto se hace leyendo el primer elemento de cada archivo, copiando hacia la salida al menor de los dos, y avanzando al siguiente elemento en el archivo respectivo. Cuando uno de los dos archivos se termina, todos los elementos restantes del otro se copian hacia la salida. Este proceso se denomina "mezcla", o bien "merge", por su nombre en inglés.
Como cada elemento se copia sólo una vez, y con cada comparación se copia algún elemento, es evidente que el costo de mezclar los dos archivos es lineal.
Si bien es posible realizar el proceso de mezcla de dos arreglos contiguos in situ, el algoritmo es muy complicado y no resulta práctico. Por esta razón, el proceso se implementa generalmente copiando de un archivo a otro.
Usando esta idea en forma reiterada, es posible ordenar un conjunto. Una forma de ver esto es recursivamente, usando "dividir para reinar". El siguiente seudo-código ilustra esta idea:
mergesort(S) # retorna el conjunto S ordenado
{
if(S es vacío o tiene sólo 1 elemento)
return(S);
else
{
Dividir S en dos mitades A y B;
A'=mergesort(A);
B'=mergesort(B);
return(merge(A',B'));
}
}
El tiempo total está dado aproximadamente por la ecuación de recurrencia
T(n) = 2 T(n/2) + n
la cual tiene solución O(n log n), de modo que el algoritmo resulta ser óptimo.
Esto mismo se puede implementar en forma no recursiva, agrupando los elementos de a dos y mezclándolos para formar pares ordenados. Luego mezclamos pares para formar cuádruplas ordenadas, y así sucesivamente hasta mezclar las últimas dos mitades y formar el conjunto completo ordenado. Como cada "ronda" tiene costo lineal y se realizan log n rondas, el costo total es O(n log n).
La idea de Mergesort es la base de la mayoría de los métodos de ordenamiento externo, esto es, métodos que ordenan conjuntos almacenados en archivos muy grandes, en donde no es posible copiar todo el contenido del archivo a memoria para aplicar alguno de los métodos estudiados anteriormente.
En las implementaciones prácticas de estos métodos, se utiliza el enfoque no recursivo, optimizado usando las siguientes ideas:
En caso que no baste con una pasada de mezcla múltiple para ordenar todo el archivo, el proceso se repite las veces que sea necesario.
Al igual que en los casos anteriores, el costo total es O(n log n).