Radix Sort, es un algoritmo que ordena enteros procesando sus dígitos de forma individual. Como los enteros pueden representar caracteres y obviamente, números flotantes, Radix Sort no está limitado únicamente a ordenar números enteros.
Ejemplo de Funcionamiento
Se tiene un grupo de números acomodados de forma aleatoria en la primera columna. Para poder acomodarlos de manera ascendente, se analizara el ultimo digito de cada número (sombreados en la columna 2), y de acuerdo al valor correspondiente a dicho digito se reacomodaran todos los números de menor a mayor, tal como se muestra en la columna dos. Terminado esto, se realizara el mismo procedimiento con el siguiente digito de todos los números (sombreados en la columna 3), y se reacomodaran nuevamente, este proceso se realizara hasta terminar con la cantidad máxima de dígitos que posea el número mayor (en los casos en los cuales un número no cuente con un digito se colocara un cero y será colocado en la primera posición).
Clasificación
Existen dos clasificaciones para 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 óptimo.
Aplicaciones del Ordenamiento Radix Sort
IBM Card Sorter.- El algoritmo Radix Sort es utilizado por las Máquinas de Clasificación de Tarjetas IBM que hoy en día se encuentran sólo en museos informáticos. Para ver un articulo explicado del funcionamiento de dichas maquinas dar click aquí.
MD5.- Este algoritmo fue desarrollado por Ronald Rivest en 1995. Con el fin de verificar que un archivo descargado esté en perfecto estado, se recurre a un algoritmo llamado MD5, el cual genera para el archivo dado un número de 32 dígitos en hexadecimal. Este número se distribuye junto con el archivo en cuestión de manera que, cuando se descargue, se puede ejecutar el mismo algoritmo y comprobar si el número resultante coincide con el número incluido en la descarga. Si es así, todo ha ido bien y el archivo se encuentra en perfecto estado. Si no, tendremos que volver a descargarlo y repetir la operación.
Tiempo de Ejecución
Radix Sort opera en un tiempo O(wn) donde:
w = cantidad de dígitos del número mayor
w = cantidad de dígitos del número mayor
n = cantidad de números a ordenar
Este tiempo de ejecución es el mismo para el mejor y peor de los casos, esto debido a que sin importar las condiciones del programa, el tiempo de ejecución del algoritmo siempre dependerá de la cantidad de dígitos del número mayor para realizar cada iteración.