DAA - Orden de Radix

Radix sortes un método pequeño que mucha gente usa intuitivamente al ordenar alfabéticamente una gran lista de nombres. Específicamente, la lista de nombres se ordena primero según la primera letra de cada nombre, es decir, los nombres se organizan en 26 clases.

De manera intuitiva, uno podría querer ordenar los números por su dígito más significativo. Sin embargo, la ordenación por Radix funciona de forma contraria a la intuición al ordenar primero los dígitos menos significativos. En la primera pasada, todos los números se ordenan por el dígito menos significativo y se combinan en una matriz. Luego, en la segunda pasada, los números completos se ordenan nuevamente en el segundo dígito menos significativo y se combinan en una matriz y así sucesivamente.

Algorithm: Radix-Sort (list, n) 
shift = 1 
for loop = 1 to keysize do 
   for entry = 1 to n do 
      bucketnumber = (list[entry].key / shift) mod 10 
      append (bucket[bucketnumber], list[entry]) 
   list = combinebuckets() 
   shift = shift * 10

Análisis

Cada tecla se mira una vez para cada dígito (o letra si las teclas son alfabéticas) de la clave más larga. Por tanto, si la clave más larga tienem dígitos y hay n llaves, la ordenación de radix tiene orden O(m.n).

Sin embargo, si miramos estos dos valores, el tamaño de las claves será relativamente pequeño en comparación con la cantidad de claves. Por ejemplo, si tenemos claves de seis dígitos, podríamos tener un millón de registros diferentes.

Aquí vemos que el tamaño de las claves no es significativo, y este algoritmo es de complejidad lineal O(n).

Ejemplo

El siguiente ejemplo muestra cómo la ordenación de Radix opera en siete números de 3 dígitos.

Entrada	1 st Pass	2 nd Pass	3 er pase
329	720	720	329
457	355	329	355
657	436	436	436
839	457	839	457
436	657	355	657
720	329	457	720
355	839	657	839

En el ejemplo anterior, la primera columna es la entrada. Las columnas restantes muestran la lista después de ordenaciones sucesivas en posiciones de dígitos cada vez más significativos. El código para la ordenación de Radix asume que cada elemento en una matrizA de n elementos tiene d dígitos, donde dígito 1 es el dígito de menor orden y d es el dígito de orden más alto.