Ordenamiento Radix

1. Algoritmo de Ordenamiento Radix
2. Ejemplo de Ordenamiento Radix
3. Implementación del Algoritmo de Ordenamiento Radix
4. Complejidad del algoritmo de Ordenamiento Radix

Ordenamiento Radix es un algoritmo de ordenación no comparativo. Este algoritmo evita las comparaciones insertando elementos en cubos de acuerdo con el radix (Radix/Base es el número de dígitos únicos utilizados para representar números. Por ejemplo, los números decimales tienen diez dígitos únicos). Ordena los elementos basándose en los dígitos de los elementos individuales. Realiza la ordenación por conteo de los dígitos desde el menos significativo hasta el más significativo. También se ha llamado ordenación en cubo o digital y es muy útil en máquinas paralelas.

Algoritmo de Ordenamiento Radix

Supongamos que tenemos un array A[] sin ordenar que contiene n elementos.

Ejemplo de Ordenamiento Radix

Supongamos que tenemos el array (1851, 913, 1214, 312, 111, 23, 41, 9). Vamos a ordenarlo utilizando el algoritmo de ordenación radix.

En la primera iteración, ordenamos según el lugar de la unidad y luego nos movemos hacia los lugares de las decenas, centenas y millares para obtener el array ordenada final como 9, 23, 41, 111, 312, 913, 1214, 1851.

Implementación del Algoritmo de Ordenamiento Radix

#include <iostream>
using namespace std;
const int N = 10;

int maxm(int arr[], int n) {
  int max = arr[0];
  for (int i = 1; i < n; i++) {
    if (arr[i] > max) {
      max = arr[i];
    }
  }
  return max;
}

void countingSort(int arr[], int n, int place) {
  int output[n];
  int count[N];

  for (int i = 0; i < N; ++i) count[i] = 0;

  for (int i = 0; i < n; i++) count[(arr[i] / place) % 10]++;

  for (int i = 1; i < N; i++) count[i] += count[i - 1];

  for (int i = n - 1; i >= 0; i--) {
    output[count[(arr[i] / place) % 10] - 1] = arr[i];
    count[(arr[i] / place) % 10]--;
  }

  for (int i = 0; i < n; i++) arr[i] = output[i];
}

void radixsort(int arr[], int n) {
  int max = maxm(arr, n);
  for (int place = 1; max / place > 0; place *= 10) countingSort(arr, n, place);
}

int main() {
  int n = 5;
  int arr[5] = {1851, 913, 1214, 312, 111};
  cout << "Input arr: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
  radixsort(arr, n);  // Sort elements in ascending order
  cout << "Output arr: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
}

Complejidad del algoritmo de Ordenamiento Radix

Complejidad temporal

• Caso medio

La ordenación radix tiene una complejidad temporal de O(n + b) donde b es el rango de entrada. Si hay d dígitos en el elemento máximo maxm, la complejidad temporal de Radix Sort es O(d*(n + b)). Como d y b suelen ser pequeños, la complejidad temporal es del orden de [Big Theta]: O(n).

• El peor caso

La complejidad temporal en el peor de los casos es del orden de [Big O]: O(n).

• El mejor caso

La complejidad temporal en el mejor de los casos es [Big Omega]: O(n). Es la misma que la complejidad temporal del peor caso.

Complejidad espacial

La complejidad espacial del algoritmo de Ordenamiento Radix es O(n+b), donde b es el rango de entrada. Proviene de los Arrays count &output en la ordenación radix. A veces b puede ser mayor que n, lo que hace que la complejidad no sea lineal.