El algoritmo de Ordenamiento por bases o Radix Sort, consiste en ordenar los números tomando en cuenta el valor relativo que tienen las cifras o dígitos de un número en un determinado sistema de numeración. La característica de este algoritmo está en que no hace comparaciones para ordenar las listas, simplemente se encarga de ir contando o agrupando los números que tengan el mismo valor relativo en determinada cifra. Se pueden ir agrupando o contando los números, desde las cifras menos significativas a las más significativas (LSD) ó en sentido contrario (MSD). El conteo o agrupación de los números se hace tomando en cuenta la base del sistema de numeración que se elija para ordenar (radix significa base).

Explicare como ordenar los siguientes números por agrupación desde las cifras menos significativas a las más significativas (LSD) en el sistema de numeración hexadecimal. Los números son: 456, 2689, 1025, 412, 482, 375 en hexadecimal serán: 1C8, A81, 401, 19C, 1E2, 177.

El método consiste en ir contando la cantidad de veces que aparece un número con determinada cifra para luego acumular los contadores y obtener la nueva posición de los números a ordenar.

Contando por la 1era cifra, la menos significativa: 1C8, A81, 401, 19C, 1E2, 177

Contando por la 2da cifra: A81 ,401 ,1E2 ,177 ,1C8 ,19C

Contando por la 3ra cifra: 401, 177, A81, 19C, 1C8, 1E2

Para la implementación de este algoritmo no usaremos un sistema de numeración hexadecimal, en su defecto se podría decir que usaremos un sistema de numeración en base 255, la razón es que cuanto más grande sea el sistema de numeración o mejor dicho cuanto más grande sea el arreglo que almacene el conteo y las posiciones de los números, el algoritmo será más rápido. Para el conteo y obtención de las posiciones usaremos un arreglo identificado con el nombre pos de 256 números de tipo Longword, la implementación constará de un procedimiento que se encargará de Contar y Posicionar los números de la lista.

El Procedimiento empieza por crear un arreglo B auxiliar que permitirá ir colocando los números de la lista en su nueva posición, se usa este arreglo auxiliar debido a que no se puede ir colocando los números en el mismo arreglo, y el tamaño de este arreglo auxiliar será del mismo tamaño que el arreglo a ordenar. Debido a que LNaturales es un arreglo dinámico de tipo qword (8 bytes), entonces el proceso de contar y posicionar se realizará 8 veces, y el encargado de hacerlo será el bucle for, si no se usará el bucle for el proceso de contar y posicionar se tendría que haber realizado del siguiente modo:

ContarPosicionar(A,B,1); //Desde la cifra menos significativa o byte menos significativo
ContarPosicionar(B,A,2);
ContarPosicionar(A,B,3);
ContarPosicionar(B,A,4);
ContarPosicionar(A,B,5);
ContarPosicionar(B,A,6);
ContarPosicionar(A,B,7);
ContarPosicionar(B,A,8); //Hasta la cifra más significativa o byte más significativo

El procedimiento ContarPosicionar es el encargado de contar y posicionar los números del arreglo A hacia el B y viceversa, el procedimiento ContarPosicionar lo primero que hace es inicializar el arreglo pos. El Procedimiento ContarPosicionar está compuesto de tres bucles for, el primero se encarga de contar obteniendo el byte o cifra correspondiente, el segundo se encarga de acumular lo contado en el arreglo pos, el tercero se encarga de colocar el numero en la nueva posición restando en 1 cada vez que se obtiene la cifra o byte del numero a posicionar.

Para obtener un determinado byte hacemos uso de un enmascaramiento, por ejemplo si queremos obtener el byte 5 desplazamos el número 24 bits a la derecha y después hacemos una operación and con el número $FF, para quedarnos con el byte que estamos buscando, algo parecido a esto:

(A shr 0) and $FF --> para el byte menos significativo ó cifra menos significativa, byte 1
(A shr 8) and $FF --> byte 2
(A shr 16) and $FF --> byte 3
(A shr 24) and $FF --> byte 4
(A shr 32) and $FF --> byte 5
(A shr 40) and $FF --> byte 6
(A shr 48) and $FF --> byte 7
(A shr 56) and $FF --> para el byte más significativo o cifra más significativa, byte 8

Como se puede observar 0, 8, 16, 24 ... 56, son una progresión aritmética que se puede implementar con facilidad del siguiente modo:

d:=(A[j] shr ((8*i)-8) and $FF;

En caso queremos ordenar la lista ascendentemente o descendentemente se debe hacer un cambio dentro del procedimiento ContarPosicionar, es decir el 3er y último bucle for, se debe cambiar según sea el caso. Para un ordenamiento ascendente se debe usar:

for j:=high(A) downto low(A) do
 Begin
   d:=(A[j] shr ((8*i)-8)) and $FF;
   pos[d]:=pos[d]-1;
   B[pos[d]]:=A[j];
 End;

Y para un ordenamiento descendente se debe usar:

for j:=low(A) to high(A) do
 Begin
   d:=(A[j] shr ((8*i)-8)) and $FF;
   pos[d]:=pos[d]-1;
   B[high(B)-pos[d]]:=A[j];
 End;

Sucede a veces que los números de una lista no necesariamente ocuparán 8 bytes, por lo que el bucle for que ejecuta el procedimiento ContarPosicionar, se puede controlar con la variable n, es decir si sabemos que los números de la lista ocupan 5 bytes entonces se debe pasar el valor 5 en el parámetro n, del procedimiento.

Debido a que cada vez que se cuenta y posiciona los números estos se van intercambiando entre los arreglos A y B, cuando la cantidad de bytes de los números a ordenar es par, es decir es: 2, 4, 6, 8; la lista quedará ordenada en el arreglo original A, pero en caso sea impar, es decir: 1, 3, 5 y 7, la lista quedará ordenada en el arreglo auxiliar B, es por eso que al final del algoritmo se encuentra la siguiente condición if:

if (n mod 2)<>0 then for i:=low(A) to high(A) do A[i]:=B[i]

Cuando usamos el algoritmo con números positivos y negativos, y ordenamos la siguiente lista: 105, -110, 150, 125, -2, estos se ordenan del siguiente modo: 105, 125, 150, -110, -2 y para remediar este situación, una solución es convertir todos los números de la lista a números positivos, eso se logra obteniendo el complemento aritmético del número. Es decir a todos los números de la lista: 105, -110, 150, 125, -2, se le resta el menor número negativo -128, obteniendo la siguiente lista: 233, 18, 278, 253, 126, se ordena la lista: 18, 126, 233, 253, 278, y para recuperar los números originales se le suma el menor número negativo -128, y se obtiene la lista ordenada: -110, -2, 105, 125, 150. En el caso los números sean de 1 byte el menor número negativos será: -128=-1*(2⁸/2), para un números de 2 bytes será: -32768=-1*(2¹⁶/2), para números 3 bytes será: -8388608=-1*(2²⁴/2) y así sucesivamente. Con lo que el algoritmo quedaría del siguiente modo:

Cuando usamos el algoritmo con números reales positivos y negativos, el comportamiento es similar a como ordenar números enteros positivos y negativos, es decir si ordenamos la siguiente lista: 10.89, -11.5, 15.0, 1.25, -2.8, estos se ordenarán del siguiente modo: 1.25, 10.89, 15.0, -11.5, -2.8 y para remediar esta situación debemos convertir los números positivos a negativos e invertir todos los bits de los números negativos. Con lo que el algoritmo quedaría del siguiente modo:

Los números reales de la lista siempre serán de 8 bytes, si queremos usar este algoritmo con un tipo de dato como el single (4 bytes), entonces se debe adaptar el procedimiento, haciendo cambios en el bucle for que ejecuta el procedimiento ContarPosicionar y en la obtención del byte o cifra de los números reales a ordenar.

La implementación de este algoritmo con una lista de cadena de caracteres, es realmente más sencillo pero su rendimiento es ineficiente cuando la longitud de las cadenas de caracteres sobrepase los 18 caracteres (sólo en Unicodestring). El siguiente procedimiento implementa el algoritmo para su uso con LPalabras:

Para obtener los caracteres simplemente se acceden de derecha a izquierda o de atrás hacia adelante, este procedimiento está diseñado sólo para ordenar palabras en mayúsculas compuestas por caracteres del alfabeto en latín. Es por eso que el arreglo pos sólo va desde 64 hasta 90, cubriendo 27 caracteres empezando e incluyendo el carácter @. Debido a que las cadenas de caracteres son de longitud variable, cuando se intente acceder a un carácter por la derecha que no existe, entonces el algoritmo debe considerarlo como un carácter @, esto es mejor que rellenar las cadenas de caracteres de @ para que todos tengan la misma longitud.

El siguiente archivo comprimido: OrdenacionPorBases.zip, tiene 4 programas de ejemplo para los tipos de datos LNaturales, LEnteros, LReales, LPalabras de la unidad listas.