Radix es un algoritmo de ordenación, sin comparación, que ordena los elementos procesando sus dígitos (representación interna, dígitos binarios bit a bit) de forma individual, agrupa los elementos por dígitos que comparten posición (unidades, decenas,…) y valor significativo. Es una generalización del algoritmo del Casillero – PigeonHole.
La primera aproximación de utilización de este algoritmo fue en 1.880 en las máquinas de tabulación de Herman Hollerith. En 1.954 Harold H. Seward lo desarrolló como un algoritmo informático exclusivamente para números enteros y elementos que se puedan convertir a este formato. Tiene una complejidad temporal de O (n×d) para el mejor, peor y promedio de los casos (d representa el número de dígitos en el mayor de los elementos).
| Rendimiento – Complejidad | |||
| Mejor caso Ω | Peor caso O | Media Θ | Espacio |
| (n × d) | (n × d) | (n × d) | O(n + d) |
El proceso de ordenación comienza tomando el último o primer dígito de cada elemento, ordenándose en base al valor de esa posición y así sucesivamente por cada dígito, hasta terminar con la cantidad máxima de dígitos que tiene cada uno de los elementos del vector. Para los elementos que no tienen la cantidad máxima de dígitos, respecto del que más dígitos tenga, se le asignará un 0 en la posición inexistente. Radix puede utilizar cualquier algoritmo para la ordenación de los dígitos de un elemento, en el ejemplo se utiliza Counting (≈Casillero) que es estable.
Básicamente hay dos tipos de Radix:
- LSD (basado en el dígito menos significativo). El LSD es estable y ordena los elementos (valor) por tamaño, las mas cortos al principio y los más largos al final.
- MSD (basado en el dígito más significativo). MSD no es del todo estable, pero se puede modificar para hacerlo. Se utiliza para ordenar palabras según el vocabulario, en el caso de encontrar una secuencia de números se ordenarán de tal forma que los veríamos así: 1, 2, 3, 31, 4, 5, 56, 57, 6, …
Implementación en lenguaje Java.
private static int[] Ordenaradix() {
int mayor = 0;
for (int i = 1; i < Vector.length; i++) {
if (Vector[i] > mayor) {
mayor = Vector[i];
}
}
int posición = 1;// desde unidades
while (mayor / posición > 0) {
ordenacontando(posición);
posición = posición * 10;
}
return Vector;
}
private static void ordenacontando(int posición){
int tamaño = Vector.length;
int[] intercambio = new int[tamaño];
int[] cuántosenlaposición = new int[10]
for(int i = 0; i < tamaño; i++){
cuántosenlaposición[(Vector[i]/posición)%10]++;
}
for(int i = 1; i < 10; i++){
cuántosenlaposición[i] = cuántosenlaposición[i] + cuántosenlaposición[i-1];
}
int indice=0;
for(int i = tamaño-1; i >=0; i--){
indice=(Vector[i]/posición)%10;
intercambio[cuántosenlaposición[indice] - 1] = Vector[i];
cuántosenlaposición[indice]--;
}
Vector=intercambio;
}
Rendimiento.
Estadística individual realizada con el mismo equipo y condiciones del resumen de estadísticas de ordenación. Como se puede ver en el gráfico, este algoritmo no es adecuado para ordenar elementos con un rango de valores grandes [1 – 100Millones]. Para un rango de valores [1 a 1.000] sí es eficiente.
