Cómo funciona
Radix Sort ordena cifra a cifra, empezando por la de las unidades (versión LSD,
least significant digit). Cada pasada es un Counting Sort con solo 10 tubos,
uno por cifra del 0 al 9: contar, acumular y colocar de derecha a izquierda. La salida de una pasada
es la entrada de la siguiente.
Counting Sort con números hasta 999 necesitaría 1000 tubos. Radix Sort reutiliza los mismos 10 tubos
tres veces.
Paso a paso con [170, 45, 75, 90, 802, 24, 2, 66]
El mayor tiene 3 cifras, así que hay 3 pasadas. Los números cortos se leen con ceros a la izquierda: 045, 002.
- 01Unidades: cifras 0, 5, 5, 0, 2, 4, 2, 6. Contar da
C = [2, 0, 2, 0, 1, 2, 1, 0, 0, 0] y la salida es [170, 90, 802, 2, 24, 45, 75, 66].
- 02Decenas:
[802, 2, 24, 45, 66, 170, 75, 90]. El 170 y el 75 tienen el mismo 7 en las decenas; el 170 sigue delante porque la pasada anterior lo dejó así (0 < 5).
- 03Centenas:
[2, 24, 45, 66, 75, 90, 170, 802]. Seis números tienen un 0 en las centenas y conservan el orden de las dos pasadas anteriores.
- ΣTotal: 0 comparaciones y 3 × (8 + 9 + 8) = 75 operaciones, d·(2n + 9). Bubble Sort, con el mismo array, haría 28 comparaciones.
Por qué empieza por las unidades
Tras la pasada de las unidades, el array está ordenado por la última cifra. La pasada de las decenas
reordena por la penúltima, y cuando dos números empatan en ella no se tocan entre sí:
Counting Sort es estable. Así el orden por unidades sobrevive dentro de cada decena, y al final el orden
por todas las cifras queda completo. Con un reparto inestable el resultado podría salir desordenado.
¿Cuándo conviene?
Su coste crece con n y con el número de cifras d, no con n·log n. Para muchos enteros de pocas cifras
(códigos postales, fechas, identificadores de longitud fija) es más rápido que cualquier algoritmo que
compare. Con claves muy largas, d crece y la ventaja desaparece.
Complejidad
- Tiempo
- O(d·(n + b))
- Comparaciones
- 0
- Espacio extra
- O(n + b)
- Estable
- Sí
- Base b
- 10 tubos
- In situ
- No