Radix sort

El siguiente video silente explica una de las versiones de radix sort (especificamente Least Significant Digit radix 10 sort)

El algoritmo que está aplicando es::

Dado: L, una lista de enteros
Resultado: L lista ordenada en orden ascendente
=====================================================
0. Determinar valor máximo en L y ajustar todos los valores
   a la cantidad de dígitos del valor máximo.
1. Inicializar 10 buckets vacíos
2. Para cada dígito d desde el least significant digit hasta el MSD:
3.   Para cada valor e en la lista:
4.     Colocar e en el bucket correspondiente al dígito en posición d 
5.   Pasar los elementos de los buckets desde el 0 hasta el 9 a la lista

Técnicamente, la complejidad de radix sort es O(mn), donde:

Dado que para la mayoría de los casos prácticos n es mucho mayor que m, podemos argumentar que radix sort es O(n).

Preguntas relacionadas

P1. Usando radix 10 sort queremos ordenar la lista L que contiene (190, 423, 899, 2134, 84, 562, 1994). ¿Cuantas pases tendrá que dar radix sort para ordenar a L? Contaremos como pase cada vez que el algoritmo recorre la lista completa distribuyendo los números en buckets?

Contestación L requiere 4 pases pues el valor máximo (2314) tiene 4 dígitos decimales.

P2. Usando radix 2 sort queremos ordenar la lista L que contiene (190, 423, 899, 2134, 84, 562, 1994). ¿Cuantas pases tendrá que dar radix sort para ordenar a L? Contaremos como pase cada vez que el algoritmo recorre la lista completa distribuyendo los números en buckets?

Contestación Al usar radix 2 solo se declaran dos buckets (0 y 1). En cada pase se distribuyen los números de acuerdo a uno de los bits. L requiere 12 pases pues el valor máximo (2314) tiene 12 dígitos binarios (100100001010).

P3 Muestra como radix sort ordena la siguiente lista L de strings usando buckets 'a', 'b', 'c', 'd'. L = (daba, baba, dada, acab, acca, caba).