Ordenamiento radix

El ordenamiento radix es la excepción entre los algoritmos de ordenamiento: nunca pregunta cuál de dos valores es mayor. Lee los números dígito a dígito y los ordena por un dígito cada vez, usando diez cubetas. La idea es más antigua que los ordenadores: así funcionaban las clasificadoras de tarjetas perforadas.

Barras de una lista sobre una fila de diez cubetas numeradas del 0 al 9; un valor cae en la cubeta de su último dígito
Barras de una lista sobre una fila de diez cubetas numeradas del 0 al 9; un valor cae en la cubeta de su último dígito

La idea

Ordena los números solo por su dígito de las unidades. Luego ordénalos por su dígito de las decenas, pero de forma que los números con el mismo dígito de las decenas sigan en el orden que les dio la primera pasada. Luego por las centenas, igual. Tras la última pasada la lista está ordenada: las centenas deciden primero, a igualdad de centenas los números ya están en orden de decenas, y a igualdad de decenas, en orden de unidades.

Una pasada, con cubetas

Cada pasada usa diez cubetas, una por cada dígito del 0 al 9. Recorre la lista de principio a fin y mueve cada número a la cubeta de su dígito, detrás de los números que ya están en ella. Luego vacía las cubetas en la lista en orden, primero la cubeta 0. Mover los números en el orden de la lista y añadirlos al final de una cubeta es lo que hace estable la pasada. La aplicación cuenta primero los números de cada dígito, para que las cubetas puedan estar una junto a otra en una sola fila, cada una justo después de la anterior: eso es un ordenamiento por cuentas sobre un dígito.

Un ejemplo

Toma 170, 45, 75, 90, 802, 24, 2, 66. Por el dígito de las unidades: 170, 90, 802, 2, 24, 45, 75, 66. Por el dígito de las decenas: 802, 2, 24, 45, 66, 170, 75, 90; fíjate en que 802 y 2, ambos con 0 en las decenas, mantienen su orden de la primera pasada. Por el dígito de las centenas: 2, 24, 45, 66, 75, 90, 170, 802. Tres pasadas sobre ocho números: 24 dígitos leídos y 48 movimientos, y ni una sola comparación.

¿Qué velocidad tiene?

Cada pasada lee un dígito de cada número y mueve cada número dos veces, así que para n números de d dígitos el trabajo crece con n · d. Un ordenamiento por comparación necesita al menos unas n log₂ n comparaciones en el peor caso, porque tiene que distinguir entre n! órdenes posibles con una pregunta de sí o no cada vez. El ordenamiento radix no está sujeto a ese límite, ya que nunca hace esas preguntas. Con muchas claves cortas, como un millón de números menores que 1000, tres pasadas suponen mucho menos trabajo que los aproximadamente 20 millones de comparaciones que necesitaría un ordenamiento por comparación. Con claves largas o pocos valores, la ventaja desaparece.

LSD y MSD, e historia

La versión que se muestra aquí empieza por el dígito menos significativo (LSD). Al revés, empezando por el dígito más significativo (MSD), se divide la lista en cubetas según el primer dígito y se ordena cada cubeta por separado, lo que va bien con cadenas de distinta longitud. El ordenamiento radix se remonta a las clasificadoras de tarjetas perforadas que siguieron a las máquinas tabuladoras de Herman Hollerith para el censo de EE. UU. de 1890: una clasificadora dejaba caer cada tarjeta en uno de diez casilleros según la perforación de una columna, y los operadores pasaban el mazo una vez por columna, empezando por la última.

Una tabuladora de tarjetas perforadas Hollerith en el Computer History Museum, del tipo usado en el censo de EE. UU. de 1890. Los operadores pasaban un mazo por un clasificador una vez por columna, el antepasado del ordenamiento radix.
Una tabuladora de tarjetas perforadas Hollerith en el Computer History Museum, del tipo usado en el censo de EE. UU. de 1890. Los operadores pasaban un mazo por un clasificador una vez por columna, el antepasado del ordenamiento radix.

Explóralo

Abre la aplicación y pulsa Paso. Cada pasada cuenta primero los dígitos, lo que marca las cubetas del 0 al 9 en la fila bajo la lista. Luego los números caen uno a uno en sus cubetas, con la cubeta activa resaltada, y se copian de vuelta. Escribe tus propios números hasta 999, como el ejemplo de arriba, para ver las tres pasadas.

Preguntas frecuentes

¿Cuál es la complejidad temporal del ordenamiento radix?

O(n · d) para n claves de d dígitos en una base fija, más el coste de las cubetas en cada pasada. Necesita O(n) de memoria extra para el búfer donde están las cubetas.

¿Es estable el ordenamiento radix?

El ordenamiento radix LSD tiene que serlo: solo funciona porque cada pasada mantiene los valores con el mismo dígito en el orden en que llegaron. Por eso el resultado final también es estable.

¿Sirve el ordenamiento radix para números negativos o decimales?

No directamente, pero sí con un truco: desplaza los números negativos para que todos sean positivos, u ordénalos aparte e invierte su orden. Los números de coma flotante se pueden ordenar por sus patrones de bits tras una pequeña transformación.

¿Por qué base 10?

Porque es fácil de seguir. Los ordenadores suelen ordenar por 8 o 16 bits a la vez, así que un número de 32 bits requiere cuatro o dos pasadas, con 256 o 65 536 cubetas.

¿Listo para probarlo?

Abre PictorX en tu navegador: sin instalación ni tarjeta de crédito para empezar.

Prueba el ordenamiento radix