Funcionamiento
Clasificación
Existen dos clasificaciones del algoritmo Radix Sort: LSD (dígito menos significativo), y MSD (dígito más significativo).
Radix sort LSD procesa los enteros empezando por el dígito menos significativo y moviéndose hacia el dígito más significativo. Radix sort MSD trabaja en sentido contrario.
Pero, ¿cuándo utilizar uno u otro?
Radix Sort MSD usa orden léxico, por lo que es ideal para la ordenación de cadenas de caracteres. Si se tiene una cadena de caracteres inicial desordenada, terminara ordenada de la siguiente manera:
[b] [c] [d] [e] [f] [g] [h] [I] [j] [ba] → [b] [ba] [c] [d] [e] [f] [g] [h] [i] [j]
Si se utiliza MSD para ordenar enteros, la ordenación de las representaciones de los números del 1 al 10 finalmente quedaría:
[1] [10] [2] [3] [4] [5] [6] [7] [8] [9]
En cambio si se utiliza el método Radix Sort LSD el arreglo quedaría ordenado como un conteo normal del 1 al 10. Por lo que concluimos que dependiendo de las necesidades del problema a resolver, el programador elegirá el algoritmo mas optimo.
Aplicación de Radix Sort
El algoritmo Radix Sort es utilizado por las Máquinas de Clasificación de Tarjetas IBM que hoy en día sólo se encuentran en museos informáticos. Su función era la de clasificar tarjetas perforadas, las tarjetas están organizadas en 80 columnas, y en cada columna un agujero puede ser perforado en uno de los 12 renglones para representar un digito. La maquina puede ser "programada" mecánicamente para examinar una columna dada de cada tarjeta en una baraja y distribuir la tarjeta en uno de los 12 contenedores que ella dispone, dependiendo del lugar que le corresponda según las perforaciones en la tarjeta. Un operador puede recolectar las cartas recipiente por recipiente, de modo que las tarjetas con el primer lugar perforado se encuentran en la parte superior de las tarjetas con el segundo lugar perforado, y así sucesivamente.
Para una mejor comprensión de lo anterior mencionado, les traemos un par de videos:
En este primer video se puede observar como se escribía en las tarjetas perforadas. Con ayuda de una maquina mecánica llamada Perforadora de Tarjetas se hacían las perforaciones dependiendo del digito que se tecleara. A partir de 1890 y a finales de 1970 dichas maquinas eran muy utilizadas en instituciones dedicadas al procesamiento de información, por lo que, al manejar una gran cantidad de datos estos debían estar ordenados/clasificados de alguna manera, es ahi donde entra el Clasificador de Tarjetas IBM, el cual funcionaba como se muestra a continuación:
Dado que el clasificador de tarjetas puede mirar una sola columna a la vez, el problema de ordenar una cantidad n tarjetas requería de un algoritmo de clasificación que tenga esta particularidad de organizar por medio de dígitos, lo cual hizo que el algoritmo Radix Sort fuera el mas adecuado a implementar en dicha maquina.
Tiempos de Ejecución
El ordenamiento radix opera en un tiempo de O(n), donde n es el numero de claves. Los Casos Peor y Mejor son también de tiempo lineal ( O(n) ) ya que Counting Sort no compara entonces da lo mismo la ordenación que ya tenga el arreglo, hace todas las operaciones de igual manera, solo que ahora repetidas d veces por el FOR de afuera de Radix Sort. Dados n números en los cuales cada digito puede tomar k posibles valores, Radix sort ordena correctamente los n números en O(d(n+k)), si d es constante y k =O(n).
Las representaciones de enteros que son procesadas por los algoritmos de ordenamiento se les llama a menudo "claves", que pueden existir por sí mismas o asociadas a otros datos.