Quicksort: Algoritmo de ordenamiento rápido

Uno de los problemas más frecuentes con los que se enfrentan los diseñadores de software es la ordenación de una lista de elementos. Ya sea que estés lidiando con una base de datos de direcciones Web, una lista de clientes o el listín telefónico de tu ciudad, seguramente necesitarás ordenarlos de alguna forma para que esos datos te sean útiles. Quicksort es el algoritmo de ordenamiento más rápido del mundo, y hoy te contamos como funciona.

¿Como harías para ordenar una lista de números elegidos al azar? Esta pregunta se la han hecho los estudiantes de todas las carreras relacionadas con la informática desde la época de las cavernas. Es un problema con el que te encuentras casi a diario, cuya resolución eficaz dista mucho de ser trivial. Pensemos un poco. Imaginemos que tenemos una caja muy larga, dividida en 100 compartimientos numerados del 1 al 100, conteniendo cada uno de ellos un papel con un número diferente anotado en él. Los papeles se encuentran distribuidos aleatoriamente, y nuestra tarea consiste en ordenarlos. Una forma simple de hacerlo consiste en utilizar una segunda caja, idéntica a la primera pero vacía. Si recorremos cien veces la caja inicial y en cada pasada nos quedamos con el número más grande que encontremos y lo pasamos al primer casillero libre de la segunda, habremos resuelto el problema. Efectivamente, luego de las cien pasadas tendremos la primer caja vacía y la segunda llena, con los números ordenados de mayor a menor en sus divisiones internas. Este sistema, a pesar de lo rudimentario y sencillo que parece, funciona perfectamente. Sin embargo, es espantosamente lento y consume una cantidad inaceptable de recursos.

Si se aplica como parte de un programa informático, el método explicado anteriormente necesita el doble de la memoria requerida para almacenar los números a ordenar, ya que hay que emplear una zona de memoria igual de grande a la que contiene el arreglo original como “destino” para los números que vamos ordenado. El tiempo implicado en la resolución del problema aumenta directamente con el numero de elementos que contenga la lista. Estos dos inconvenientes no son importantes en listas pequeñas, pero se vuelven muy importantes cuando la lista contiene miles de millones de elementos. Si tenemos en cuenta que a finales del siglo pasado un estudio demostró que más de la mitad del total del tiempo de cómputo utilizado por todos los ordenadores del mundo se empleaba en “ordenar cosas” (no es casualidad que a nuestros computadores los llamemos “ordenadores”), nos damos cuenta de la importancia que tiene disponer de un algoritmo que resuelva estas cuestiones de forma eficiente. El explicado anteriormente no es en absoluto eficaz, pero afortunadamente existen otros mucho más inteligentes. El más famoso de ellos quizás sea el denominado Quicksort.

Este algoritmo fue propuesto por Sir Charles Antony Richard Hoare en 1960. Hoare no sólo encontró una forma muy ingeniosa para ordenar elementos, sino que además logró una demostración matemática que prueba que este sistema es en realidad el más rápido posible, por lo que desde hace más de 50 años la discusión de que pasos conviene seguir para ordenar una lista ha dejado de tener sentido. La respuesta es siempre la misma: Quicksort. Antes de ver como hace su magia este algoritmo, tenemos que comprender un concepto -muy utilizado por los informáticos- llamado recursividad. La recursividad es la es la forma en la cual se especifica un proceso basado en su propia definición.  Para ponerlo más claro podemos ver un ejemplo:  “la suma de los números de 1 a n es igual a la suma de 1 a (n-1) + n” En la frase anterior existe la recursividad. Se nos dice que para sumar una serie de números, basta con sumar el último de la lista a la suma de todos los anteriores. Obviamente, para obtener esa suma parcial puede aplicarse el mismo procedimiento, una y otra vez, hasta llegar a una lista que solo contiene el “1”. La posibilidad de definir la solución de un problema recurriendo a la propia definición se llama recursividad. Es sumamente útil, aunque debe prestarse mucha atención para evitar que un pequeño error de programación nos atrape en un bucle infinito. Comprendido esto, veamos como funciona Quicksort.

El secreto de Quicksort consiste en dividir la lista original en dos listas más pequeñas. Para ello, se elige un elemento cualquiera (aunque en general se suele utilizar el que se encuentra en medio de la lista) que nos servirá como pivote. Luego se recorre toda la lista, con el objeto de colocar los elementos más pequeños que el pivote a la izquierda del mismo, y los mayores a la derecha. Las implementaciones más eficientes realizan esta tarea a la vez, recorriendo simultáneamente la lista en ambas direcciones e intercambiando entre sí cada par de elementos “descolocados” que se encuentran a su paso. Culminada esta etapa tenemos un grupo de elementos menores que el pivote, el pivote, y otro grupo compuesto por números mayores a él. En este punto es donde juega un papel importante la recursividad: si cada uno de esos grupos vuelve a dividirse en dos y se aplica lo explicado anteriormente de forma recursiva, tenemos resuelto el problema. Lo mejor de todo es que el tamaño de las sublistas -y por ende el tiempo que se necesita para procesarlas- es cada vez menor.  En cada nivel el tamaño de las sublistas la mitad del anterior, lo que permite ordenar una lista de 1024 elementos en 10 “pasadas”, y una de más de un millón en solo 20. Y lo mejor de todo es que no requiere de una “segunda caja vacía” sobre la que ordenar los elementos, con lo que el consumo de recursos (memoria) es menor.

Otra innegable ventaja del algoritmo Quicksort es que puede ser paralelizado. ¿Que significa esto? Que en ordenadores con más de un microprocesador -algo muy común en los superordenadores que, justamente, son los que suelen realizar procesos como estos con cantidades enormes de elementos- el problema puede dividirse en muchas partes pequeñas y cada una ser resuelta por una CPU diferente. Esta característica también es importante cuando el numero de elementos es tan grande que no pueden mantenerse todos en la memoria RAM del ordenador encargado de ordenarlos. En ese caso, Quicksort permite ir guardando en un subsistema de almacenamiento externo cada porción ordenada, y al final juntar todo para tener la lista completa. Por supuesto, no todo son rosas: este algoritmo es fuertemente dependiente de la “suerte” que hayamos tenido al elegir el elemento pivote. Si somos tan burros como para elegir un elemento que se encuentre en uno de los extremos de la lista, habremos dividido el problema en dos partes muy dispares (una con solo un elemento, ya ordenada, y otra casi del mismo tamaño que la original, desordenada) y el algoritmo no será tan eficiente. Este problema puede minimizarse mediante diferentes estrategias, como el primer elemento, el último y el central, y hallar el promedio entre los tres (suponiendo que sean números). Otro enfoque es, antes de cada pasada, recorrer toda la lista de valores buscando el mejor valor posible para el pivote. Esto es óptimo, pero en listas largas costoso en términos de tiempo. A pesar de este costado flaco, Quicksort es uno de los algoritmos más estudiados y optimizados del mundo de la informática. ¿Lo conocías?