Definicion de Radix Sort
Es un algoritmo de ordenamiento que ordena enteros procesando sus dígitos de forma individual. Como los enteros pueden representar cadenas de caracteres (por ejemplo, nombres o fechas) y, especialmente, números en punto flotante especialmente formateados, radix sort no está limitado sólo a los enteros.
Este método se puede considerar como una generalización de la clasificación por urnas.
Consiste en hacer diversos montones de fichas, cada uno caracterizado por tener en sus componentes un mismo digito (letra si es alfabética) en la misma posición; estos montones se recogen en orden ascendente y se reparte en montones según el siguiente digito de la clave.
Clasificación (Formas de utilizar Radix Sort)
-- El de dígito menos significativo (LSD) .
-- El de dígito más significativo (MSD).
Radix sort LSD procesa las representaciones de 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.
REGLAS PARA ORDENAR
Empezar enel dígito menos significativo y avanzar por los dígitos menos significativos mientras coinciden los dígitos correspondientes en los dos números.
El número con el dígito más grande en la primera posición en la cual los dígitos de los dos números no coinciden es el mayor de los dos (por supuesto sí coinciden todos los dígitos de ambos números, son iguales).
Se debe conocer el numero de diferentes valores posibles en cualquier posicion.
*******************************************************************************************************************************
Ejemplo: Ordenacion empezando por el bit menos significativo
Vector Original: 25 57 48 37 12 92 86 33
En la primera evaluacion tomaremos el bit menos significativo de nuestros datos en el caso del primero digito que es el 25 el bit menos significativo es el 5 y el mas significativo es el 2 tomando en cuenta tus posiciones y asi se empieza con la ordenacion continuando con el 57 y asi consecutivamente como se muestra a continuacion.
25 En este caso 5 es el menos significativo
0
1
2 12 , 92
3 33
4
5 25
6 86
7 57 , 37
8 48
9
Ahora nuestro Vector es : 12 92 33 25 86 57 37 48
En la segunda evaluacion tomaremos el bit mas significativo en nuestro caso seria el 2do digito 12
si el caso fuera que tuvieramos un 100 o un digito con mas de 3 cifras o caracteres tomariamos el 2do bit que seria 100.
Segunda evaluacion.
0
1 12
2 25
3 33 , 37
4 48
5 57
6
7
8 86
9 92
Y nuestra lista ya ordenada e s
Vector ordenado: 12 25 37 48 57 86 92
En el caso de empezar nuestra ordenacion por la forma del dígito más significativo (MSD) seria la misma dinamica solo que tomariamos en este caso 100 el bit mas significativo que es el 1.