Clasificación Radix en Java

En esta guía, aprenderá la teoría detrás de Radix Sort y Counting Sort a través de ejemplos visuales, ¡y también implementará ambos en Java!

Introducción

Sorting es una de las técnicas fundamentales utilizadas en la resolución de problemas, especialmente en aquellos relacionados con la escritura e implementación de algoritmos eficientes.

Por lo general, la clasificación se combina con la búsqueda, lo que significa que primero clasificamos elementos en la colección dada, luego buscamos algo dentro de ella, ya que generalmente es más fácil buscar algo en una colección ordenada, en lugar de una sin clasificar, ya que puede hacer conjeturas informadas e imponer suposiciones sobre los datos.

Hay muchos algoritmos que pueden ordenar elementos de manera eficiente, pero en esta guía veremos cómo implementar Radix Sort en Java.

Clasificación Radix en Java

Radix Sort es un algoritmo de clasificación no comparativo, lo que significa que no clasifica una colección comparando cada uno de los elementos dentro de ella, sino que se basa en algo llamado radix para clasificar la colección.

La raíz (a menudo llamada base) es el número de dígitos únicos en un sistema numérico posicional, que se usa para representar números.

Para el conocido sistema binario, la base es 2 (utiliza solo dos dígitos: 0 y 1). Para el sistema decimal posiblemente aún más conocido, la base es 10 (utiliza diez dígitos para representar todos los números, del 0 al 9).

¿Cómo utiliza Radix Sort esto en beneficio propio?

Radix Sort no ordena por sí mismo, en realidad. Utiliza cualquier algoritmo de clasificación estable y no comparativo como su subrutina y, en la mayoría de los casos, la subrutina es Clasificación por conteo.

clasificación estable

Si n representa el número de elementos que debemos ordenar, y k es el rango de valores permitidos para esos elementos, la complejidad de tiempo de Counting Sort es O(n+k) cuando k está en oscila entre 1...n, que es significativamente más rápido que el típico algoritmo de clasificación comparativa con una complejidad de tiempo de O(nlogn).

Pero el problema aquí es - si el rango es 1...n², la complejidad del tiempo se deteriora drásticamente a O(n²) muy rápidamente.

La idea general de Radix Sort es ordenar dígito por dígito desde los menos significativos hasta los más significativos (LSD Radix Sort) y también se puede hacer al revés (*MSD Radix Sort *). Permite que Counting Sort haga lo mejor posible dividiendo la entrada y ejecutando Counting Sort varias veces en conjuntos que no permiten que k se acerque a .

Debido a que no se basa en la comparación, no está limitado por O (nlogn), incluso puede funcionar en tiempo lineal.

Dado que el trabajo pesado lo realiza Counting Sort, primero avancemos y echemos un vistazo a cómo funciona e implementé, ¡antes de sumergirnos en Radix Sort!

Clasificación por recuento en Java: teoría e implementación {#clasificación por recuento en la teoría y la implementación de Java}

Counting Sort es un algoritmo de clasificación no comparativo, estable, y su uso principal es para clasificar matrices de enteros.

La forma en que funciona es que cuenta la cantidad de objetos que tienen valores clave distintos y luego aplica una suma de prefijo en esos mismos recuentos para determinar la posición de cada valor clave en la salida. Al ser estable, el orden de los registros con claves iguales se conserva cuando se ordena la colección.

Esta operación da como resultado, esencialmente, una lista de ocurrencias de enteros, que normalmente llamamos arreglo de conteo. Counting Sort usa el arreglo de conteo auxiliar para determinar las posiciones de los elementos:

Cada índice en la matriz de salida representa un elemento en la matriz de entrada. El valor asociado con este índice es el número de ocurrencias (el conteo) del elemento en la matriz de entrada.

La mejor manera de mostrar cómo funciona Counting Sort es a través de un ejemplo. Consideremos que tenemos la siguiente matriz:

1
int[] arr = {3, 0, 1, 1, 8, 7, 5, 5};

En aras de la simplicidad, utilizaremos dígitos del 0 al 9. El valor máximo de un dígito que podemos tener en cuenta es obviamente 9, por lo que estableceremos un max = 9.

Esto es importante porque necesitamos una matriz auxiliar adicional que consta de elementos max + 1. Esta matriz se usará para contar el número de apariciones de cada dígito dentro de nuestra matriz arr, por lo que debemos inicializar toda la matriz de conteo countingArray a 0.

1
2
int[] countingArray = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
// there are 10 digits, so one zero for every element

Ahora que hemos definido la matriz con la que trabajaremos e inicializado la matriz de conteo, debemos realizar los siguientes pasos para implementar la ordenación por conteo:

1. Recorriendo nuestra matriz arr y contando la ocurrencia de cada elemento individual mientras se incrementa el elemento en la posición arr[i] en nuestra matriz countingArray:

1
2
for(int i = 0; i < arr.length; i++)
    countingArray[arr[i]]++;

Después de este paso, countingArray tiene los siguientes elementos: [1, 2, 0, 1, 0, 2, 0, 1, 1, 0].

2. El siguiente paso es aplicar sumas de prefijos en countingArray, y obtenemos lo siguiente:

1
2
for(int i=1; i < countingArray.length; i++)
    countingArray[i] += countingArray[i-1];

Después de la modificación de la matriz de conteo, ahora consta de countingArray = {1, 3, 3, 4, 4, 6, 6, 7, 8, 8}.

3. El tercer y último paso es calcular las posiciones de los elementos en la salida ordenada según los valores de countingArray. Para eso, necesitaremos una nueva matriz que llamaremos outputArray, y la inicializaremos en m ceros, donde m es el número de elementos en nuestra matriz original arr:

1
2
int[] outputArray = {0, 0, 0, 0, 0, 0, 0, 0};
// there are 8 elements in the arr array

Dado que Counting Sort es un algoritmo de clasificación estable, estaremos iterando a través de la matriz arr en orden inverso, para que no terminemos cambiando los elementos.

Encontraremos el índice en nuestro countingArray que es igual al valor del elemento actual arr[i]. Luego, en la posición countingArray[arr[i]] - 1 colocaremos el elemento arr[i].

Esto garantiza la estabilidad de este tipo, además de colocar cada elemento en su posición correcta en el orden ordenado. Luego, disminuiremos el valor de countingArray[i] en 1.

Al final, copiaremos outputArray a arr para que los elementos ordenados estén contenidos dentro de arr ahora.

Unifiquemos todos estos fragmentos e implementemos completamente la ordenación por conteo:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
int[] arr = {3, 0, 1, 1, 8, 7, 5, 5};
int[] countingArray = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};

for(int i = 0; i < arr.length; i++)
    countingArray[arr[i]]++;

for(int i=1; i < countingArray.length; i++)
    countingArray[i] += countingArray[i-1];

int[] outputArray = {0, 0, 0, 0, 0, 0, 0, 0};
for(int i = arr.length-1; i >= 0; i--){
    outputArray[countingArray[arr[i]] - 1] = arr[i];
    countingArray[arr[i]]--;
}

for(int i = 0; i < arr.length; i++){
    arr[i] = outputArray[i];
    System.out.print(arr[i] + " ");
}

Ejecutar esto nos dará una matriz ordenada:

1
0, 1, 1, 3, 5, 5, 7, 8

Como se mencionó anteriormente, la complejidad temporal de este algoritmo es O(n+k), donde n es el número de elementos en arr y k es el valor del elemento max en la matriz. Sin embargo, a medida que k se acerca a , este algoritmo se deteriora hacia O(n²), que es una desventaja importante del algoritmo.

Ya que explicamos brevemente cómo funciona Counting Sort, pasemos al tema principal de este artículo: Radix Sort.

Radix Sort en Java: teoría e implementación

Una vez más, Radix Sort suele contar la clasificación como una subrutina, por lo que Radix Sort también es un algoritmo de clasificación estable.

Las claves utilizadas por Counting Sort serán los dígitos de los enteros dentro de la matriz que estamos ordenando.

Hay dos variantes de Radix Sort: una que ordena a partir del Dígito menos significativo (LSD) y la segunda que ordena a partir del Dígito más significativo (MSD). Nos centraremos en el enfoque LSD.

Radix Sort por sí mismo no es muy complicado de entender una vez que entendemos cómo funciona Counting Sort, por lo que los pasos para implementarlo son bastante simples:

  1. Busque el elemento max en la matriz de entrada.
  2. Determine el número de dígitos, d, que tiene el elemento max. El número d representa cuántas veces revisaremos la matriz usando Ordenar por conteo para ordenarla.
  3. Inicialice el número s a 1 al principio, representando el lugar menos significativo y aumentando su valor multiplicándolo por 10 cada vez.

Por ejemplo, digamos que tenemos la siguiente matriz de entrada arr = {73, 481, 57, 23, 332, 800, 754, 125}. El número de veces que recorreremos la matriz es 3, ya que el elemento max en nuestra matriz arr es 800, que tiene 3 dígitos.

Veamos un ejemplo visual de una matriz que se ordena de esta manera, paso a paso, para ver cómo Radix Sort ordena los elementos en cada iteración:

La matriz de entrada se divide en los dígitos que componen sus elementos originales. Luego, ya sea usando el dígito más significativo y avanzando hacia abajo, o el dígito menos significativo y avanzando hacia arriba, la secuencia se ordena a través de Clasificación por conteo:

En la primera pasada, solo se usa el lado derecho para ordenar, y es por eso que la estabilidad en Radix Sort/Counting Sort es clave. Si no hubiera estabilidad, no tendría sentido clasificar de esta manera. En el segundo paso, usamos la fila del medio y, finalmente, se usa la fila de la izquierda y la matriz se ordena por completo.

Finalmente, implementemos Radix Sort:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
static void radixSort(int[] arr) {
  int max = arr[0];
  for (int i = 1; i < arr.length; i++) {
    if (max < arr[i])
      max = arr[i];
  }

  for (int s = 1; max / s > 0; s *= 10)
    countingSortForRadix(arr, s);
}

También querremos modificar ligeramente Countinng Sort.

Esta modificación de Counting Sort hace exactamente lo mismo que la implementación anterior, solo que se enfoca en dígitos en diferentes lugares de los enteros a la vez:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
static void countingSortForRadix(int[] arr, int s) {
  int[] countingArray = {0,0,0,0,0,0,0,0,0,0};
  for (int i = 0; i < arr.length; i++)
    countingArray[(arr[i] / s) % 10]++;

  for (int i = 1; i < 10; i++)
    countingArray[i] += countingArray[i - 1];

  int[] outputArray = {0,0,0,0,0,0,0,0};
  for (int i = arr.length - 1; i >= 0; i--)
    outputArray[--countingArray[(arr[i] / s) % 10]] = arr[i];

  for (int i = 0; i < arr.length; i++)
    arr[i] = outputArray[i];
}

Vamos a crear una matriz e intentar ordenarla ahora:

1
2
3
4
5
6
7
public static void main(String[] args) {
  int[] arr = {73,481,57,23,332,800,754,125};

  radixSort(arr);
  for (int i = 0; i < arr.length; i++)
    System.out.print(arr[i] + " ");
}

Esto resulta en:

1
23, 57, 73, 125, 332, 481, 754, 800

Dado que estamos usando Counting Sort como la subrutina principal, para una matriz que contiene n elementos, que tiene el elemento max con d dígitos, en un sistema con una base b, tenemos la complejidad de tiempo de O(d(n+b)).

Eso es porque estamos repitiendo el proceso Ordenar por conteo d veces, que tiene una complejidad O(n+b).

Conclusión

Aunque Radix Sort puede funcionar de manera muy eficiente y maravillosa, requiere algunos casos específicos para hacerlo. Debido a que requiere que represente los elementos que se ordenarán como números enteros, es fácil ver por qué algunos otros algoritmos de clasificación basados ​​en comparación pueden resultar ser una mejor opción en muchos casos.

Los requisitos de memoria adicionales de Radix Sort en comparación con otros algoritmos basados ​​en comparación también son una de las razones por las que este algoritmo de clasificación se usa con menos frecuencia.

Por otro lado, este algoritmo funciona magníficamente cuando la matriz de entrada tiene teclas más cortas o el rango de elementos es más pequeño.

Licensed under CC BY-NC-SA 4.0