Algoritmos de ordenación

Ayer por la tarde me puse manos a la obra a programar radix sort en C++. La implementación que venía en la Wikipedia era una cacola que provocaba violaciones de segmento.

Para quien nunca haya oído hablar de él, el radix sort es un algoritmo de ordenación O(n). Sí, sí, es más rápido que el quicksort o el merge sort. El truco es que no hace comparaciones entre elementos. En vez de eso, genera una especie de histograma y lo aprovecha para saber en qué posición queda cada elemento en la lista ordenada. Es una idea muy ingeniosa. Lo malo es que requiere una cantidad de memoria extra O(n), mientras que el quicksort se conforma con O(log n).

Aunque la implementación que hice trata de ser lo más simple posible para que sea fácil de leer, en la tarea de ordenar 100 millones de enteros de 32 bits el radix sort en mi ordenador tarda algo menos de la mitad que el introsort que viene con la librería estándar de C++. Diez segundos contra veintiuno.

He subido mi código a la wikipedia. Podéis verlo aquí.

Más tarde si tengo ganas os enseñaré un algoritmo de ordenación que se me ocurrió ayer. Si no me fallan las cuentas, requiere un tiempo O(Mⁿ n! n²), donde n es la longitud de la lista, y M es la cardinalidad del conjunto de donde vienen los elementos de la lista. Por ejemplo, si la lista es de enteros entre 1 y 10, entonces M=10. Traté de ordenar una lista de siete elementos entre 1 y 10 pero me cansé de esperar.