Ordenar por Radix en Java

1. Introducción

En este tutorial, aprenderemos sobre Radix Sort, analizaremos su rendimiento y veremos su implementación.

Aquí nos enfocamos en usar Radix Sort para ordenar números enteros, pero no se limita solo a números. También podemos usarlo para ordenar otros tipos como String .

Para hacerlo simple, nos centraremos en el sistema decimal en el que los números se expresan en base (raíz) 10.

2. Descripción general del algoritmo

La ordenación por radix es un algoritmo de ordenación que ordena los números en función de las posiciones de sus dígitos. Básicamente, usa el valor posicional de los dígitos en un número. A diferencia de la mayoría de los otros algoritmos de clasificación, como Merge Sort, Insertion Sort, Bubble Sort, no compara los números.

La ordenación por radix utiliza un algoritmo de ordenación estable como subrutina para ordenar los dígitos. Hemos utilizado una variación del ordenamiento de conteo como una subrutina aquí que usa la base para ordenar los dígitos en cada posición. La clasificación de conteo es un algoritmo de clasificación estable y funciona bien en la práctica.

La ordenación por radix funciona clasificando los dígitos desde el dígito menos significativo (LSD) hasta el dígito más significativo (MSD). También podemos implementar la ordenación Radix para procesar dígitos desde MSD.

3. Un ejemplo rápido

Veamos cómo funciona con un ejemplo. Consideremos la siguiente matriz:

Iteración 1:

Ordenaremos esta matriz procesando dígitos de LSD y moviéndonos hacia MSD.

Así que comencemos con los dígitos en el lugar de las unidades:

Después de la primera iteración, la matriz ahora se ve así:

Tenga en cuenta que los números se han ordenado según los dígitos en el lugar de las unidades.

Iteración 2:

Pasemos a los dígitos en el lugar de las decenas:

Ahora la matriz se ve así:

Vemos que el número 7 ha ocupado la primera posición en la matriz ya que no tiene ningún dígito en el lugar de las decenas. También podríamos pensar que esto tiene un 0 en el lugar de las decenas.

Iteración 3:

Pasemos a los dígitos en la posición de las centenas:

Después de esta iteración, la matriz se ve así:

Y el algoritmo se detiene aquí, con todos los elementos ordenados.

4. Implementación

Veamos ahora la implementación.

void sort(int[] numbers) { int maximumNumber = findMaximumNumberIn(numbers); int numberOfDigits = calculateNumberOfDigitsIn(maximumNumber); int placeValue = 1; while (numberOfDigits-- > 0) { applyCountingSortOn(numbers, placeValue); placeValue *= 10; } }

El algoritmo funciona averiguando el número máximo en la matriz y luego calculando su longitud. Este paso nos ayuda a asegurarnos de ejecutar la subrutina para cada valor posicional.

Por ejemplo, en la matriz [7, 37, 68, 123, 134, 221, 387, 468, 769] , el número máximo es 769 y su longitud es 3.

Entonces, iteramos y aplicamos la subrutina tres veces en los dígitos en cada posición:

void applyCountingSortOn(int[] numbers, int placeValue) { int range = 10 // decimal system, numbers from 0-9 // ... // calculate the frequency of digits for (int i = 0; i < length; i++) { int digit = (numbers[i] / placeValue) % range; frequency[digit]++; } for (int i = 1; i 
    
     = 0; i--) { int digit = (numbers[i] / placeValue) % range; sortedValues[frequency[digit] - 1] = numbers[i]; frequency[digit]--; } System.arraycopy(result, 0, numbers, 0, length); }
    

En la subrutina, usamos la base (rango) para contar la ocurrencia de cada dígito e incrementar su frecuencia. Entonces, cada bin en el rango de 0 a 9 tendrá algún valor basado en la frecuencia de dígitos. Luego usamos la frecuencia para posicionar cada elemento en la matriz. Esto también nos ayuda a minimizar el espacio requerido para ordenar la matriz.

Ahora probemos nuestro método:

@Test public void givenUnsortedArray_whenRadixSort_thenArraySorted() { int[] numbers = {387, 468, 134, 123, 68, 221, 769, 37, 7}; RadixSort.sort(numbers); int[] numbersSorted = {7, 37, 68, 123, 134, 221, 387, 468, 769}; assertArrayEquals(numbersSorted, numbers); }

5. Ordenar por Radix vs Ordenar por Conteo

En la subrutina, la longitud de la matriz de frecuencias es 10 (0-9). En el caso de Counting Sort, no usamos el rango . La longitud de la matriz de frecuencia será el número máximo en la matriz + 1. Por lo tanto, no los dividimos en contenedores, mientras que Radix Sort usa los contenedores para clasificar.

Contando Ordenar es bastante eficiente cuando la longitud de la matriz no es mucho menor que el valor máximo en la matriz, mientras que Radix Sort permite valores más grandes en la matriz.

6. Complejidad

El rendimiento de Radix Sort depende del algoritmo de clasificación estable elegido para ordenar los dígitos.

Aquí hemos usado Radix Sort para ordenar una matriz de n números en base b . En nuestro caso, la base es 10. Hemos aplicado el orden de conteo d veces donde d representa el número de dígitos. Entonces, la complejidad de tiempo de Radix Sort se convierte en O (d * (n + b)) .

La complejidad del espacio es O (n + b) ya que aquí hemos utilizado una variación de Ordenar contando como subrutina.

7. Conclusión

En este artículo, describimos el algoritmo de ordenación Radix e ilustramos cómo implementarlo.

Como de costumbre, las implementaciones de código están disponibles en Github.