Los algoritmos de ordenación

Los algoritmos de ordenación son los procedimientos con los que un ordenador pone una lista en orden, y constituyen el problema más estudiado de la historia de la informática: Donald Knuth le dedicó medio volumen de The Art of Computer Programming y estimó en los años setenta que los ordenadores del mundo pasaban más de una cuarta parte de su tiempo ordenando. Hay decenas de métodos, y la razón de que no baste con uno es que ninguno es el mejor en todas las circunstancias. La figura de esta página pone a cuatro de ellos a ordenar la misma lista a la vez, operación a operación, para que se vea en qué se diferencian y por qué el ganador cambia según los datos.

Los cuatro corredores representan las dos grandes familias. La ordenación por burbuja y la ordenación por inserción son métodos cuadráticos: en el peor caso, el número de operaciones crece con el cuadrado del tamaño de la lista, de modo que ordenar diez veces más elementos cuesta cien veces más. La ordenación por mezcla y la ordenación rápida son métodos de divide y vencerás: partan la lista en trozos, ordenan cada trozo y combinan los resultados, y su coste crece solo un poco más rápido que el tamaño de la lista, en proporción a n por el logaritmo de n. Con cuarenta elementos la diferencia es visible; con un millón es la diferencia entre un segundo y varias horas.

La burbuja recorre la lista comparando cada elemento con el siguiente e intercambiándolos si están en el orden incorrecto, de manera que el mayor «sube» hasta el final en cada pasada, como una burbuja en el agua. Es el primer algoritmo que se enseña y probablemente el peor que se usa: Knuth escribió que «no parece tener nada que lo recomiende, salvo un nombre pegadizo», y Owen Astrachan rastreó en 2003 el origen de su popularidad hasta los manuales de los años sesenta sin encontrar ninguna virtud técnica que la justificara. En la figura se aprecia su defecto característico: los elementos pequeños que están al final avanzan solo una posición por pasada, así que una lista al revés le exige el máximo de trabajo posible.

La inserción hace lo que hace una persona con una mano de cartas: toma el siguiente elemento y lo desplaza hacia la izquierda hasta que encuentra su sitio entre los que ya están ordenados. También es cuadrática en el peor caso, pero con una diferencia decisiva: si la lista está casi ordenada, cada elemento se mueve muy poco y el algoritmo termina en un tiempo casi proporcional al tamaño de la lista. Al elegir «casi ordenados» en la figura, la inserción gana la carrera con claridad a los dos métodos teóricamente superiores. Por eso sigue viva dentro de casi todos los algoritmos modernos, que la usan para rematar los trozos pequeños.

La ordenación por mezcla divide la lista por la mitad, ordena cada mitad —dividiéndola a su vez— y después fusiona las dos mitades ordenadas recorriéndolas en paralelo y tomando en cada paso el menor de los dos frentes. John von Neumann la describió en 1945 para el EDVAC. Su virtud es la regularidad: hace el mismo número de operaciones sea cual sea el orden inicial de los datos, y es estable, es decir, dos elementos iguales conservan su orden relativo, cosa que importa cuando se ordena una tabla primero por una columna y luego por otra. Su coste es que necesita una segunda lista auxiliar del mismo tamaño para ir depositando la fusión, y en la figura se distingue porque escribe mucho más de lo que intercambia.

La ordenación rápida, o quicksort, la inventó Tony Hoare en 1959, con veinticinco años, mientras estaba en Moscú como estudiante de intercambio trabajando en traducción automática y necesitaba ordenar palabras para buscarlas en un diccionario en cinta. Elige un elemento como pivote, coloca a su izquierda todos los menores y a su derecha todos los mayores, y repite el proceso en cada uno de los dos lados. En la figura el pivote es la barra naranja de la derecha del tramo sombreado, y se ve cómo va a parar a su posición definitiva en cada ronda. Es en promedio el más rápido de los cuatro y no necesita memoria auxiliar, pero tiene un talón de Aquiles: si el pivote resulta ser siempre el mayor o el menor —como ocurre con la versión más simple sobre una lista ya ordenada o invertida—, la partición es inútil y el algoritmo cae al coste cuadrático. Hoare mismo propuso elegir el pivote al azar para evitarlo, y las versiones modernas toman la mediana de tres elementos.

Se puede demostrar que ningún algoritmo que ordene comparando elementos entre sí puede hacerlo, en el peor caso, con menos operaciones que una cantidad proporcional a n por el logaritmo de n: ordenar n elementos es distinguir entre las n! permutaciones posibles, y cada comparación descarta como mucho la mitad. La mezcla y la rápida están, por tanto, en el óptimo teórico, y la carrera entre ellas se decide por las constantes, por el uso de memoria y por la forma de los datos. Solo saliéndose de las comparaciones —contando ocurrencias, o mirando los dígitos de los números uno a uno, como hace la ordenación por radix— se puede ir más deprisa, y solo para tipos de datos concretos.

Los algoritmos que ordenan de verdad hoy son híbridos que sacan partido de cada carril de la figura. Timsort, que Tim Peters escribió en 2002 para Python y que Java adoptó en 2009 y Android después, es una mezcla que detecta los tramos ya ordenados de la lista —que en los datos reales abundan— y los fusiona con inteligencia, recurriendo a la inserción para los tramos cortos. Es tan complejo que en 2015 un grupo de investigadores que intentaba verificarlo formalmente encontró en la implementación de Java un error que llevaba seis años en producción y que podía hacer que el programa fallara con ciertas entradas raras. Los algoritmos de ordenación, sesenta años después de Hoare, siguen dando trabajo.