algoritmo de busqueda radix sort

concepto

Es un algoritmo 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.

descripcion
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.

clasificacion
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.
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.
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.

clasificacion
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.
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.



ejemplo
Vector original:

25 57 48 37 12 92 86 33

Asignamos los elementos en colas basadas en el dígito menos significativo de cada uno de ellos.

0:

1:

2: 12 92

3: 33

4:

5: 25

6: 86

7: 57 37

8: 48

9:

Después de la primera pasada, la ordenación queda:

12 92 33 25 86 57 37 48

Colas basadas en el dígito más significativo.

0:

1: 12

2: 25

3: 33 37

4: 485: 57

6:

7:

8: 86

9: 92

Lista ordenada:

12 25 33 37 48 57 86 92