¿Qué es Counting Sort?

Counting Sort es un algoritmo de ordenamiento no comparativo que funciona contando la cantidad de ocurrencias de cada elemento en un arreglo. Utiliza esta información para construir el arreglo ordenado de manera eficiente.

El Código

                
function countingSort(arr) {
  const max = Math.max(...arr);
  const min = Math.min(...arr);
  const range = max - min + 1;

  const count = Array(range).fill(0);
  const output = Array(arr.length).fill(0);

  // Contar la ocurrencia de cada elemento
  for (let i = 0; i < arr.length; i++) {
    count[arr[i] - min]++;
  }

  // Modificar el array count para almacenar la posición de los elementos
  for (let i = 1; i < count.length; i++) {
    count[i] += count[i - 1];
  }

  // Construir el array de salida
  for (let i = arr.length - 1; i >= 0; i--) {
    output[count[arr[i] - min] - 1] = arr[i];
    count[arr[i] - min]--;
  }

  // Copiar el array de salida al array original
  for (let i = 0; i < arr.length; i++) {
    arr[i] = output[i];
  }

  return arr;
}

// Ejemplo de uso
const array = [4, 2, 2, 8, 3, 3, 1];
console.log("Array ordenado:", countingSort(array));
                
            

Puntos Clave del Algoritmo

• Entrada: Un arreglo de números enteros (arr).
• Salida: El arreglo ordenado de menor a mayor.
• Método:
  • Cuenta la cantidad de ocurrencias de cada elemento usando un arreglo auxiliar (count).
  • Calcula las posiciones de cada elemento acumulando los valores en count.
  • Construye el arreglo ordenado copiando los valores al arreglo original basado en las posiciones calculadas.
• Complejidad:
  • Tiempo: O(n + k), donde n es el tamaño del arreglo y k es el rango de valores.
  • Espacio: O(n + k) debido al uso de arreglos auxiliares.
• Ventajas: Es eficiente para arreglos con un rango limitado de valores.
• Desventajas: No es adecuado para datos con valores grandes o flotantes debido a los altos costos de memoria.

Ejemplo de Ejecución

Arreglo inicial: [4, 2, 2, 8, 3, 3, 1]

Proceso de ordenamiento:

1. Contar las ocurrencias: count = [1, 2, 2, 1, 0, 1, 0, 0, 1]
2. Acumular las posiciones: count = [1, 3, 5, 6, 6, 7, 7, 7, 8]
3. Construir el arreglo ordenado: output = [1, 2, 2, 3, 3, 4, 8]

Arreglo final ordenado: [1, 2, 2, 3, 3, 4, 8]

Información Adicional

Counting Sort es ideal para aplicaciones en las que los datos tienen un rango limitado de valores. Es particularmente útil para ordenar números enteros no negativos, pero requiere modificaciones para datos negativos o flotantes.