Algoritmo de clasificación Radix en estructura de datos

¿Qué es el algoritmo de clasificación Radix?

Radix Sort es un algoritmo de clasificación no comparativo. Funciona agrupando los dígitos individuales de los elementos a ordenar. Luego se utiliza una técnica de clasificación estable para organizar los elementos según su base. Es un algoritmo de clasificación lineal.

El proceso de clasificación involucra las siguientes propiedades:

Encontrar el elemento máximo y adquirir el número de dígitos de ese elemento. Nos da el número de iteraciones que seguirá el proceso de clasificación.
Agrupe los dígitos individuales de los elementos en la misma posición significativa en cada iteración.
El proceso de agrupación comenzará desde el dígito menos significativo y finalizará en el dígito más significativo.
Ordenar los elementos según los dígitos en esa posición significativa.
Mantener el orden relativo de los elementos que tienen el mismo valor clave. Esta propiedad del tipo de base lo convierte en un tipo estable.

La iteración final nos dará una lista completamente ordenada.

Funcionamiento del algoritmo de clasificación Radix

Intentemos ordenar la lista de números enteros en la figura anterior en orden ascendente usando el algoritmo Radix Sort.

Estos son los pasos para realizar el proceso de clasificación Radix:

Paso 1) Identifique el elemento con el valor máximo en la lista. En este caso es 835.

Paso 2) Calcula el número de dígitos del elemento máximo. 835 tiene 3 dígitos exactamente.

Paso 3) Determine el número de iteraciones según el paso 2. 835 tiene 3 dígitos, lo que significa que el número de iteraciones será 3.

Paso 4) Determinar la base de los elementos. Como se trata de un sistema decimal, la base será 10.

Paso 5) Inicie la primera iteración.

a) Primera iteración

En la primera iteración, consideramos el valor posicional unitario de cada elemento.

Paso 1) Modifica el número entero en 10 para obtener el lugar unitario de los elementos. Por ejemplo, 623 mod 10 nos da el valor 3 y 248 mod 10 nos da 8.

Paso 2) Utilice la clasificación por conteo o cualquier otra clasificación estable para organizar los números enteros según su dígito menos significativo. Como se ve en la figura, 248 caerán en el octavo cubo. 8 caerá en el tercer cubo y así sucesivamente.

Después de la primera iteración, la lista ahora tiene este aspecto.

Como puede ver en la figura anterior, la lista aún no está ordenada y requiere más iteraciones para estar completamente ordenada.

b) Segunda iteración

En esta iteración, consideraremos el dígito en el 10^th lugar para el proceso de clasificación.

Paso 1) Divide los números enteros entre 10. 248 dividido entre 10 nos da 24.

Paso 2) Modifique la salida del paso 1 por 10. 24 mod 10 nos da 4.

Paso 3) Siga el paso 2 de la iteración anterior.

Después de la segunda iteración, la lista ahora se ve así

Puede ver en la figura anterior que la lista aún no está completamente ordenada porque aún no está en orden ascendente.

c) Tercera iteración

Para la iteración final, queremos obtener el dígito más significativo. En este caso son los 100^thlugar para cada uno de los números enteros de la lista.

Paso 1) Dividimos los números enteros entre 100… 415 dividido entre 100 nos da 4.

Paso 2) Modifica el resultado del paso 1 por 10. 4 mod 10 nos da 4 nuevamente.

Paso 3) Siga el paso 3 de la iteración anterior.

Como podemos ver, la lista ahora está ordenada en orden ascendente. La iteración final se completó y el proceso de clasificación ya finalizó.

Pseudocódigo del algoritmo de clasificación Radix

Aquí está el pseudocódigo para el algoritmo de clasificación Radix

radixSortAlgo(arr as an array)
  Find the largest element in arr
  maximum=the element in arr that is the largest
  Find the number of digits in maximum
  k=the number of digits in maximum 
  Create buckets of size 0-9 k times
for j -> 0 to k
  Acquire the j^th place of each element in arr. Here j=0 represents the least significant digit.
  Use a stable sorting algorithm like counting sort to sort the elements in arr according to the digits of the elements in the j^thplace
   arr = sorted elements

C++ Programa para implementar Radix Sort

#include <iostream>
using namespace std;
// Function to get the largest element in an array
int getMaximum(int arr[], int n) {
  int maximum = arr[0];
  for (int i = 1; i < n; i++) {
    if (maximum < arr[i]) maximum = arr[i];
  }
  return maximum;
}
// We are using counting sort to sort the elements digit by digit
void countingSortAlgo(int arr[], int size, int position) {
  const int limit = 10;
  int result[size];
  int count[limit] = {0};
  // Calculating the count of each integers
  for (int j = 0; j < size; j++) count[(arr[j] / position) % 10]++;
  // Calculating the cumulative count
  for (int j = 1; j < limit; j++) {
    count[j] += count[j - 1];
  }
  // Sort the integers
  for (int j = size - 1; j >= 0; j--) {
    result[count[(arr[j] / position) % 10] - 1] = arr[j];
    count[(arr[j] / position) % 10]--;
  }
  for (int i = 0; i < size; i++) arr[i] = result[i];
}
// The radixSort algorithm
void radixSortAlgo(int arr[], int size) {
  // Get the largest element in the array
  int maximum = getMaximum(arr, size);
  for (int position = 1; maximum / position > 0; position *= 10)
    countingSortAlgo(arr, size, position);
}
// Printing final result
void printResult(int arr[], int size) {
  for (int i = 0; i < size; i++) {
    cout << arr[i] << " ";
  }
  cout << endl;
}
int main() {
  int arr[] = {162, 623, 835, 415, 248};
  int size = sizeof(arr) / sizeof(arr[0]);
  radixSortAlgo(arr, size);
  printResult(arr, size);
}

Salida:

162 248 415 623 835

Python Programa para el algoritmo de clasificación Radix

#Radix Sort using python
def countingSortAlgo(arr, position):
    n = len(arr)
    result = [0] * n
    count = [0] * 10  # Calculating the count of elements in the array arr
    for j in range(0, n):
        element = arr[j] // position
        count[element % 10] += 1  # Calculating the cumulative count
    for j in range(1, 10):
        count[j] += count[j - 1]  # Sorting the elements
    i = n - 1
    while i >= 0:
        element = arr[i] // position
        result[count[element % 10] - 1] = arr[i]
        count[element % 10] -= 1
        i -= 1
    for j in range(0, n):
        arr[j] = result[j]


def radixSortAlgo(arr):  # Acquiring the largest element in the array
    maximum = max(arr)  # Using counting sort to sort digit by digit
    position = 1
    while maximum // position > 0:
        countingSortAlgo(arr, position)
        position *= 10


input = [162, 623, 835, 415, 248]
radixSortAlgo(input)
print(input)

Salida:

[162,248,415,623,835]

Análisis de complejidad de Radix Sort

Hay dos tipos de complejidad a considerar: la complejidad espacial y la complejidad temporal.

Complejidad espacial: O(n+b) donde n es el tamaño de la matriz y b es la base considerada.
Complejidad temporal: O(d*(n+b)) donde d es el número de dígitos del elemento más grande de la matriz.

Complejidad espacial de la clasificación por radix

Dos características en las que centrarse para la complejidad espacial

Número de elementos en la matriz, n.
La base para representar los elementos, b.

A veces esta base puede ser mayor que el tamaño de la matriz.

La complejidad general es entonces O(n+b).

Las siguientes propiedades de los elementos de la lista pueden hacer que el espacio de ordenación por radio sea ineficiente:

Elementos con una gran cantidad de dígitos.
La base de los elementos es grande, como números de 64 bits.

Complejidad temporal de la ordenación por radix

Puede utilizar la ordenación por conteo como subrutina, ya que cada iteración tomarámi O(n+b) tiempo. Si existen iteraciones, el tiempo total de ejecución se convierte en O(d*(n+b)). Aquí, “O” significa la función de complejidad.

Linealidad del tipo Radix

Radix Sort es lineal cuando

d es constante, donde d es el número de dígitos del elemento más grande.
b no es mayor en gran medida en comparación con n.

Comparaciones de Radix Sort con otros algoritmos comparativos

Como hemos visto, la complejidad del ordenamiento por radix se basa en el tamaño de una palabra o un número. Tendrá la misma complejidad para el caso promedio y el mejor, que es O(d*(n+b)). Además, difiere según la técnica de ordenamiento que utilice en el medio. Por ejemplo, puede utilizar el ordenamiento por conteo o el ordenamiento rápido para el algoritmo de ordenamiento intermedio dentro del ordenamiento por radix.

Aplicaciones del algoritmo de clasificación Radix

Las aplicaciones importantes de Radix Sort son:

Radix Sort se puede utilizar como algoritmo de búsqueda de ubicación donde se utilizan grandes rangos de valores.
Se utiliza para construir una matriz de sufijos en el algoritmo DC3.
Se utiliza en una máquina secuencial de acceso aleatorio presente en una computadora típica donde se ingresan los registros.