Algoritmos de ordenación

Me había propuesto un post largo sobre este tema pero siguiendo la máxima «no reinventes la rueda» he decidido hacer un artículo más chico y recomendaros encarecidamente el sitio web Sorting Algorithms en su lugar. Aquí, no sólo encontrareis los métodos de ordenación más comunes sino que además contreis con animaciones, pseudocódigo, complejidad, comparativa… Qué más se puede pedir.

La ordenación de elementos es uno de los primeros problemas que pueden verse en la ingeniería informática. Involucra muchos conceptos importantes como el buen orden, la notción O, casos medio, mejor y peor, etc

Empezaremos por definir el orden de una lista de elementos diciendo:

Una lista está ordenada si sus elementos están en orden creciente sin importarnos si dos elementos son iguales.

Ahora vamos a definir escuétamente algunas características importantes de clasificación:

• Complejidad. Quizá la más importante. Se refiere al tiempo empleado en completar la ordenacion. En principio se considera un buen tiempo aquellos pertenecientes a O(n log n) y malos, a los pertenecientes a O(n^2). De nuevo es importante aquí la notación O. Se deben considerar los casos mejor, peor y medio.
• Uso de memoria. A parte de lo que ocupe la lista, cuánto espacio extra se necesita para ejecutar el algoritmo. Realmente es otra medida de complejidad así que seguiremos utilizando la notación O para cuantificarlo.
• Adaptabilidad. Si la list que nos dan YA está ordenada, entonces el algoritmo de ordenación debería tardar menos (a fin de cuentas tendrá que comprobarla pero no reordenarla) pero esto no siempre es así. Un algoritmo de ordenación es adaptable si adapta su ejecución al estado actual de la lista.

Otras medidas que suelen aportarse es su complejidad computacional (el número de operaciones como comparaciones o cambios) y la estabilidad (imagina que ordenas pares (X, Y) por el primer elemento del par; se trata de la capacidad de mantener dos pares con el mismo primer elemento en el mismo orden que en la lista original).

Método de Inserción

El método de inserción recorre una lista tomando el elemento actual e insertándolo donde toque entre los que ya ha recorrido. Su complejidad es de O(n^2) en el peor de los casos pero es adaptativo y cuando los elementos se encuentran casi ordenados se convierte en O(n). Además casi no consume memoria extra.

Se utiliza cuando el problema es pequeño y de hecho, se utiliza como caso base de otros métodos de ordenación basados en divide y vencerás, cuando los conjuntos en los que queda dividido el problema son pequeños.

for i = 2:n,
    for (k = i; k > 1 and a[k] < a[k-1]; k--)
        swap a[k,k-1]
    → invariant: a[1..i] is sorted
end

Fuente y animación: http://www.sorting-algorithms.com/insertion-sort

En serio, os recomiendo encarecidamente las animaciones.

Método de la Burbuja

Este método se parece mucho al de inserción (mismas complejidades y adaptabilidad) pero es algo más complejo. Parte del hecho de que lo que lleva recorrido no sólo está ordenado sino que está en su posición final y no habrá que cambiarlo. Se llama de la burbuja porque los elementos flotan hasta su posición correcta como lo harían las burbujas de una bebida gaseosa.

Aquí la cosa consiste en recorrer la lista al revés tratando de encontrar el elemento más bajo y dejarlo al principio de la lista. Ahora que ya tenemos el más bajo colocado, nos vamos a por el segundo (que, si nos damos cuenta, es el mismo problema si ignoramos el primero) y así sucesivamene.

Para encontrar el más pequeño, el recorrido inverso toma un elemento y el siguiente. Como recorremos la lista al revés, se espera que dos elementos estén ordenados si se encuentran como actual=grande y siguiente=pequeño. Si es así, no se hace nada y el actual pasa a ser el pequeño. Si no es así y tenemos actual=pequeño y siguiente=grande, se les da la vuelta y se continúa. Así, el pequeño va flotando hasta el comienzo de la lista.

Esto nos lleva a un coste en O(n^2) pero cuando los elementos están casi ordenados, los cambios extra producidos durante los sucesivos recorridos habrá tendido a colocar en su sitio los elementos desordenados por lo que la complejidad se reduce a O(n) y por tanto, hablamos de un algoritmo adaptativo.

for i = 1:n,
    swapped = false
    for j = n:i+1,
        if a[j] < a[j-1],
            swap a[j,j-1]
            swapped = true
    → invariant: a[1..i] in final position
    break if not swapped
end

Esa condición de parada, debajo del comentario, lo que viene a decir es que si nos se produce ningún cambio, todo está en su lugar y podemos parar.

Fuente y animación: http://www.sorting-algorithms.com/bubble-sort

Método de Selección

El primo tonto de los métodos de ordenación. ¿En qué consiste? Bueno, se busca el menor entre todos y se coloca al principio, luego se hace lo mismo con el resto; y otra vez; y otra vez…

El método de selección es el caso general del de la burbuja. La principal deiferencia es que el algoritmo por selección no es adaptativo. En su recorrido para seleccionar el más bajo, así como el de la burbuja al menos daba la vuelta a los pares desordenados; el algoritmo de selecciónal no hace nada y la complejidad siempre es O(n^2). Ahora bien (tenía que haber algo bueno) minimiza el número de cambios.

for i = 1:n,
    k = i
    for j = i+1:n, if a[j] < a[k], k = j
    → invariant: a[k] smallest of a[i..n]
    swap a[i,k]
    → invariant: a[1..i] in final position
end

Fuente y animación: http://www.sorting-algorithms.com/selection-sort

Método Shell

Este método es muy ingenioso, consiste en aplicar el método de inserción sobre sublistas de la lista original, comenzando por pocos elementos poco ordenados y terminando en muchos elementos pero casi ordenados.

Para seleccionar la sublista se cuenta cada h elementos donde h varía desde el número de elementos de la lista hasta 1. Por ejemplo, considera la secuencia [5, 7, 9, 12, 3, 6, 8, 4, 5, 6, 3, 15, 17]. Si h = 13, cuenta 13 elementos y tendrás la sublista [17]. Si h = 3, cuenta cada 3 elementos y la sublista será [9, 6,5, 15]. Ahora tomando h = 2, obtenemos [7, 12, 6, 4, 6, 15] y si h = 1 entonces la lista es la original.

La idea es utilizar el método de inserción para ordenar cada sublista. Cada paso dejará la lista original más ordenada y el último paso es una inserción normal y corriente con una lista casi ordenada (caso donde el algoritmo se comporta mejor).

h = 1
while h < n, h = 3*h + 1
while h > 0,
    h = h / 3
    for k = 1:h, insertion sort a[k:h:n]
    → invariant: each h-sub-array is sorted
end

Fuentes y animación:

http://www.sorting-algorithms.com/merge-sort

http://en.wikipedia.org/wiki/Shell_sort

Método de Mezcla o Merge

El método de mezcla es muy fácil de entender. Consiste en partir la lista en dos, ordenarla y mezclar las sublistas ordenadas de nuevo en una sola.

¿Cómo se ordena cada sublista? Como quieras.

Una forma es aplicando de nuevo el método de mezcla. Se vuelve a dividir hasta que las sublistas o sean vacias ([]) o sean de un sólo elemento ([42]). Entonces puedes decir que están (trivialmente) ordenadas. El método se convierte en recursivo porque aplica el mismo algoritmo a subproblemas más sencillos.

Se ve bastante bien en esta animación de Wikipedia:

Método por mezcla

Lo bueno de la ordenación por mezcla es que es muy predictivo. Su complejidad es siempre de O(n·log n) y requiere un espacio de O(log n) en memoria devido a la recursividad. No es adaptativo pero es estable. De hecho es el único algoritmo en O(n·log n) que es estable.

# split in half
m = n / 2

# recursive sorts
sort a[1..m]
sort a[m+1..n]

# merge sorted sub-arrays using temp array
b = copy of a[1..m]
i = 1, j = m+1, k = 1
while i <= m and j <= n,
    a[k++] = (a[j] < b[i]) ? a[j++] : b[i++]
    → invariant: a[1..k] in final position
while i <= m,
    a[k++] = b[i++]
    → invariant: a[1..k] in final position

Del algoritmo, la parte con más chicha es la de mezcla. Mezclar dos listas ordenadas consiste en llevar dos cursores, uno que recorra los elementos de la lista A y otro para la lista B. La idea es comparar elemento a elemento añadiendo siempre el valor más bajo y avanzando el cursor.

Se ve muy bien en la última parte de la ordenación de la animación: mezclar [1, 3, 5, 6] y [2, 4, 7, 8]

• Entre el 1 y el 2 se coge el 1 y se avanza el cursor de la primera.
• Ahora entre el 3 y el 2 se coge el 2 y se avanza el cursor de la segunda.
• Entre 3 y 4 se coge el 3 y se avanza el cursor de la primera.
• Entre el 5 y el 4 se coge el 4 y se avanza el cursor de la segunda.
• Entre el 5 y el 7 se coge el 5 y se avanza el cursor de la primera.
• Entre el 6 y el 7 se coge el 6 y se avanza el cursor de la primera otra vez.
• Sólo quedan elementos  de la segunda y se añaden al final. Es decir, se añaden el 7 y el 8.

Fuentes y animaciones:

http://www.sorting-algorithms.com/merge-sort

http://en.wikipedia.org/wiki/Merge_sort

Método Rápido o Quick Sort

La ordenación rápida es «la panacea» de los algoritmos de ordenación pero hay que ser crítico con ella.

En muchos cursos de ingeniería se nombra como el mejor de los algoritmos de ordenación cuando, curiosamente, su complejidad está en O(n^2) y no es ni adaptativo ni estable. El truco aquí es que está en que es rápido en la mayoría de las veces y cuando es rápido es muy rápido y su complejidad está en O(n·log n).

La idea es obtener un pivote y conseguir que todos los números a la izquierda del pivote sean menores que él y todos los números a la derecha del pivote sean mayores que él. Luego cada sublista resultado de dividir la original por el pivote se ordena recursivamente. ¿Cómo? De nuevo como quieras pero puedes usar, al igual que en el método por mezcla, una solución recursiva y volver a elegir un pivote en cada una de las sublistas, dejar los menores a un lado y los mayores a otro y repetir hasta que las listas sean de 1 o 0 elementos (momento en el cual están trivialmente ordenadas).

El método recursivo necesita un espacio de memoria extra en el orden de O(log n).

# choose pivot
swap a[1,rand(1,n)]

# 2-way partition
k = 1
for i = 2:n, if a[i] < a[1], swap a[++k,i]
swap a[1,k]
→ invariant: a[1..k-1] < a[k] <= a[k+1..n]

# recursive sorts
sort a[1..k-1]
sort a[k+1,n]

La partición se hace eligiendo un pivote y trantando de colocarlo en el lugar adecuado habiendo hecho los cambios necesarios para que todos los elementos previos sean menores que él (ojo que no significa que estén ordenados) y los elementos posteriores, mayores.

Para ello se elige un pivote al azar y se mueve al comienzo de la lista. Luego se establece que su posición temporal será esa y se comprueban el resto de elementos. Si uno de ellos es menor, se incrementa la posición en la que se colocará el pivote (tiene sentido, se incrementa porque el elemento que hemos encontrado es menor y tenemos que dejar hueco para él) y se cambia el elemento a ese lugar (podríamos mover el pivote a su nueva posición y el elemento que hemos encontrado a la posición anterior del pivote pero esto es hacer cambios innecesarios como veremos poco después). Si el elemento es más alto, se deja donde está y la posición del pivote no se mueve.

Al final tendremos el lugar dónde va el pivote y allí habrá un elemento menor que él por lo que bastará intercambiar este con el pivote para lograr la partición que nos proponíamos.

La línea vertical indica el valor del pivote.

La elección del pivote es importante pues es la que puede llevar la complejidad del algoritmo a O(n^2). Esto sucede para pivotes elegidos al azar. Las alternativas son tomar el elemento que realmente vaya a ir en medio o tomar varios pivotes, hacer una media y elegir el que más se acerque a ella.

Este algoritmo tiene una variante con dos pivotes llamada 3-way quick sort o método rápido de 3 vías. Los principios son muy similares (pero la lista queda dividida en las dos sublistas anteriores y una tercera en medio con todos los elementos iguales) y se vuelve bastante adaptativo en listas con muchas repeticiones.

Fuentes y animaciónes:

http://www.sorting-algorithms.com/quick-sort

http://es.wikipedia.org/wiki/Quicksort

Método del Montículo o Heap Sort

El método del montículo consiste en utilizar esta estructura de datos como base para establecer el orden. Un montículo es un árbol binario dónde todo subárbol izquierdo es menor que la raíz y todo subárbol derecho es mayor que la raíz.

Lo primero que se hace es transforma la lista en un montículo o heap, Luego se extrae la raíz del árbol  se coloca al final de la lista. A continuación se regerena el heap y se vuelve a hacer lo mismo hasta que todos los elementos son extraídos del montículo.

Método del montículo. Primero la lista se convierte en un montículo y luego se extrae el elemento raíz cada vez.

# heapify
for i = n/2:1, sink(a,i,n)
→ invariant: a[1,n] in heap order

# sortdown
for i = 1:n,
    swap a[1,n-i+1]
    sink(a,1,n-i)
    → invariant: a[n-i+1,n] in final position
end

# sink from i in a[1..n]
function sink(a,i,n):
    # {lc,rc,mc} = {left,right,max} child index
    lc = 2*i
    if lc > n, return # no children
    rc = lc + 1
    mc = (rc > n) ? lc : (a[lc] > a[rc]) ? lc : rc
    if a[i] >= a[mc], return # heap ordered
    swap a[i,mc]
    sink(a,mc,n)

Explicaremos cómo se crea un montículo en uno de los siguientes artículos. Por el momento basta saber que el algoritmo actúa siempre en O(n·log n) y no es realmente adaptativo ya que la conversión a montículo normalmente está reñida con la obtención del elemento superior y, aunque las dos fases resultan adaptativas por sí solas, juntas no producen ninguna mejora.

Fuentes y animaciones:

http://www.sorting-algorithms.com/heap-sort

http://es.wikipedia.org/wiki/Heapsort

Conclusiones

Hay más. A parte de estos, existe una familia de algoritmos para ordenar enteros que no actúan mediante comparaciones y que tienen tiempos mucho más cortos.

En cuanto a estos, los métodos por mezcla y rápido parecen los mejores y de entre ellos dos, el método por mezcla es el que, particularmente, más me gusta. Es previsible, estable y siempre rápido. Ahora bien, la experimentación demuestra que en el caso medio, el método rápido desempeña mejor que el método por mezcla y con una elección cuidadosa del pivote y puestos a aceptar algo de sobrecarga podríamos eliminar la posibilidad de obtener tiempor en O(n^2).

Los algoritmos recursivos tienen una ventaja magnífica y es que nos permiten combinar varios métodos de orden. Por ejemplo, para ordenar una lista muy, muy grande de enteros podríamos separarla en varias y luego mezclarlas con el método por mezcla. Además cada sublista podría ser orenada por un método rápido recursivo que, para cuando las sublistas fuesen muy pequeñas, utilizaría un algoritmo de inserción.