¿Qué es Radix Sort?

Radix Sort es un algoritmo de ordenamiento no comparativo que organiza números procesando cada dígito individualmente, comenzando desde el dígito menos significativo (LSD) hasta el más significativo (MSD). Es eficiente para arreglos grandes de números enteros.

El Código

                
function getMax(arr) {
  let max = arr[0];
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] > max) {
      max = arr[i];
    }
  }
  return max;
}

function countingSortForRadix(arr, exp) {
  const n = arr.length;
  const output = new Array(n).fill(0);
  const count = new Array(10).fill(0);

  for (let i = 0; i < n; i++) {
    const index = Math.floor(arr[i] / exp) % 10;
    count[index]++;
  }

  for (let i = 1; i < 10; i++) {
    count[i] += count[i - 1];
  }

  for (let i = n - 1; i >= 0; i--) {
    const index = Math.floor(arr[i] / exp) % 10;
    output[count[index] - 1] = arr[i];
    count[index]--;
  }

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

function radixSort(arr) {
  const max = getMax(arr);

  for (let exp = 1; Math.floor(max / exp) > 0; exp *= 10) {
    countingSortForRadix(arr, exp);
  }

  return arr;
}

// Ejemplo de uso
const array = [170, 45, 75, 90, 802, 24, 2, 66];
console.log("Array ordenado:", radixSort(array));
                
            

Puntos Clave del Algoritmo

• Entrada: Un arreglo de números enteros (arr).
• Salida: El arreglo ordenado de menor a mayor.
• Método:
  • Encuentra el número más grande del arreglo (getMax).
  • Ordena los números dígito por dígito usando countingSortForRadix.
  • Itera desde el dígito menos significativo (LSD) hasta el más significativo (MSD).
• Complejidad:
  • Tiempo: O(nk), donde n es el número de elementos y k es el número de dígitos del número más grande.
  • Espacio: O(n + k) debido al uso de arreglos temporales.
• Ventajas: Es más rápido que algoritmos basados en comparación como Quick Sort para datos con un rango de valores limitado.
• Desventajas: Es específico para números y requiere espacio adicional para contar y organizar los dígitos.

Ejemplo de Ejecución

Arreglo inicial: [170, 45, 75, 90, 802, 24, 2, 66]

Proceso de ordenamiento:

1. Ordena por el dígito menos significativo (LSD): [170, 90, 802, 2, 24, 45, 75, 66]
2. Ordena por el segundo dígito: [802, 2, 24, 45, 66, 170, 75, 90]
3. Ordena por el tercer dígito: [2, 24, 45, 66, 75, 90, 170, 802]

Arreglo final ordenado: [2, 24, 45, 66, 75, 90, 170, 802]

Información Adicional

Radix Sort es ideal para conjuntos de datos donde los números tienen un rango de valores limitado y fijo. A menudo se utiliza en aplicaciones que requieren ordenar grandes cantidades de números rápidamente.