Counting Sort: La Guía Definitiva de Ordenación

En el vasto universo de la informática, los algoritmos de ordenación son herramientas fundamentales que nos permiten organizar datos para procesarlos de manera más eficiente. Mientras que algoritmos como Quick Sort o Merge Sort se basan en la comparación de elementos, existe una familia de algoritmos que sigue un enfoque completamente diferente. Uno de los más notables y eficientes de este grupo es el Counting Sort o algoritmo de ordenación por conteo. Este método se aleja de las comparaciones y, en su lugar, utiliza las propias claves de los elementos como índices en un arreglo auxiliar para determinar su posición final. A lo largo de este artículo, desglosaremos su funcionamiento, exploraremos sus propiedades y te mostraremos cuándo y cómo puedes implementarlo para llevar el rendimiento de tus aplicaciones al siguiente nivel.

¿Qué es Exactamente el Algoritmo Counting Sort?

El Counting Sort es un algoritmo de ordenación que opera en tiempo lineal, O(n+k), bajo ciertas condiciones. A diferencia de los algoritmos basados en comparación, que tienen un límite inferior de O(n log n), Counting Sort no compara elementos entre sí. En su lugar, funciona contando el número de ocurrencias de cada objeto de clave distinta en el arreglo de entrada. Luego, utiliza estas cuentas para calcular las posiciones de cada objeto en el arreglo de salida.

La condición fundamental para poder utilizar este algoritmo es que los valores del arreglo de entrada deben ser enteros y estar dentro de un rango conocido y relativamente pequeño. Por ejemplo, si sabemos que vamos a ordenar una lista de edades de personas, es probable que los valores estén en un rango de 0 a 120, lo cual es perfecto para este método. Sin embargo, si el rango de valores fuera extremadamente grande (por ejemplo, de 0 a mil millones), el algoritmo se volvería ineficiente en términos de uso de memoria.

Funcionamiento de Counting Sort: Un Ejemplo Paso a Paso

Para entender verdaderamente cómo funciona, nada mejor que un ejemplo práctico. Imaginemos que tenemos el siguiente arreglo de números que queremos ordenar:

Entrada: [2, 5, 3, 1, 4, 2]

El proceso se puede dividir en los siguientes pasos:

Paso 1: Encontrar el rango de los datos

Primero, identificamos el valor máximo en nuestro arreglo de entrada. En este caso, el valor máximo es 5. Esto nos dice que los números van del 0 al 5 (asumiendo que el mínimo es 0 o 1). Este rango, que llamaremos k, es crucial para el siguiente paso.

Paso 2: Crear un arreglo de conteo (o frecuencia)

Creamos un nuevo arreglo, que llamaremos conteo, de tamaño k+1 (es decir, 6, para los índices del 0 al 5). Inicializamos todos sus elementos a cero. Este arreglo almacenará la frecuencia de cada número en el arreglo de entrada.

conteo = [0, 0, 0, 0, 0, 0]
Índices: 0 1 2 3 4 5

Paso 3: Llenar el arreglo de conteo

Recorremos el arreglo de entrada y, por cada elemento, incrementamos el valor en el índice correspondiente del arreglo conteo.

• El primer elemento es 2, así que incrementamos conteo[2].
• El segundo es 5, incrementamos conteo[5].
• Y así sucesivamente con todos los elementos.

Después de recorrer todo el arreglo de entrada, nuestro arreglo conteo se verá así:

conteo = [0, 1, 2, 1, 1, 1]
Índices: 0 1 2 3 4 5

Esto nos dice que hay: cero '0', un '1', dos '2', un '3', un '4' y un '5'.

Paso 4: Construir el arreglo de salida

Ahora, simplemente recorremos el arreglo conteo y construimos nuestro arreglo de salida. Por cada índice, añadimos ese número al arreglo de salida tantas veces como indique su frecuencia.

• Índice 0: conteo[0] es 0, no hacemos nada.
• Índice 1: conteo[1] es 1, añadimos un '1' a la salida. Salida: [1]
• Índice 2: conteo[2] es 2, añadimos dos '2' a la salida. Salida: [1, 2, 2]
• Índice 3: conteo[3] es 1, añadimos un '3' a la salida. Salida: [1, 2, 2, 3]
• Índice 4: conteo[4] es 1, añadimos un '4' a la salida. Salida: [1, 2, 2, 3, 4]
• Índice 5: conteo[5] es 1, añadimos un '5' a la salida. Salida: [1, 2, 2, 3, 4, 5]

¡Y listo! El arreglo está ordenado. Este método es simple, pero no es estable. Una versión más robusta, que garantiza la estabilidad (mantener el orden relativo de elementos iguales), modifica el paso 3 y 4.

Versión Estable de Counting Sort

Para hacer el algoritmo estable, se añade un paso intermedio:

Paso 3.5 (Modificar el arreglo de conteo): Se modifica el arreglo conteo para que cada elemento en un índice i contenga la suma de las cuentas anteriores. Esto nos dará la posición final de cada elemento en el arreglo de salida.

conteo original = [0, 1, 2, 1, 1, 1]

conteo modificado = [0, 1, 3, 4, 5, 6] (Ej: conteo[2] ahora es 3, porque 0+1+2=3)

Paso 4 (Construir la salida de forma estable): Se crea un arreglo de salida vacío del mismo tamaño que el de entrada. Se recorre el arreglo de entrada desde el final hacia el principio. Para cada elemento, se busca su posición en el conteo modificado, se coloca en la salida y se decrementa el valor en conteo. Esto asegura que elementos iguales se coloquen en el orden en que aparecieron originalmente.

Propiedades y Complejidad del Algoritmo

Analizar las propiedades de un algoritmo es clave para decidir si es el adecuado para nuestro problema.

Ventajas y Desventajas de Counting Sort

Ventajas

• Extremadamente Rápido: Su complejidad de tiempo lineal O(n+k) lo hace uno de los algoritmos más rápidos para los casos de uso adecuados.
• Estable: Preserva el orden original de los elementos iguales, una propiedad crucial para algoritmos más complejos como Radix Sort.
• Sencillo de Implementar: La lógica básica detrás del conteo de frecuencias es relativamente fácil de entender y codificar.

Desventajas

• Limitado a Enteros: No funciona directamente con tipos de datos como cadenas de texto o números de punto flotante.
• Dependiente del Rango: Su rendimiento y viabilidad dependen de que el rango (k) de los datos de entrada no sea significativamente mayor que el número de elementos (n).
• Consumo de Memoria: Puede ser muy ineficiente en términos de espacio si el rango de valores es grande. Ordenar `[1, 1000000]` requeriría un arreglo de conteo de un millón de elementos.

Implementaciones en Diferentes Lenguajes

A continuación, se muestra cómo implementar la versión estable de Counting Sort en JavaScript y C++.

JavaScript

function countingSort(arr) { if (arr.length === 0) { return []; } // Encontrar el valor máximo para determinar el tamaño del arreglo de conteo let max = Math.max(...arr); const count = new Array(max + 1).fill(0); const output = new Array(arr.length); // 1. Almacenar la frecuencia de cada elemento for (let i = 0; i < arr.length; i++) { count[arr[i]]++; } // 2. Modificar el arreglo de conteo para almacenar posiciones finales for (let i = 1; i <= max; i++) { count[i] += count[i - 1]; } // 3. Construir el arreglo de salida de forma estable for (let i = arr.length - 1; i >= 0; i--) { output[count[arr[i]] - 1] = arr[i]; count[arr[i]]--; } return output;}const numbers = [1, 4, 1, 2, 7, 5, 2];console.log("Arreglo original:", numbers);console.log("Arreglo ordenado:", countingSort(numbers)); // [1, 1, 2, 2, 4, 5, 7]

C++

#include #include #include void printVector(const std::vector& vec) { for (int num: vec) { std::cout << num << " "; } std::cout << std::endl;}void countingSort(std::vector& arr) { if (arr.empty()) { return; } // Encontrar el valor máximo y mínimo para manejar el rango int max = *std::max_element(arr.begin(), arr.end()); int min = *std::min_element(arr.begin(), arr.end()); int range = max - min + 1; std::vector count(range, 0); std::vector output(arr.size()); // 1. Almacenar la frecuencia de cada elemento (ajustando por el mínimo) for (int i = 0; i < arr.size(); i++) { count[arr[i] - min]++; } // 2. Modificar el arreglo de conteo para almacenar posiciones finales for (int i = 1; i < count.size(); i++) { count[i] += count[i - 1]; } // 3. Construir el arreglo de salida de forma estable for (int i = arr.size() - 1; i >= 0; i--) { output[count[arr[i] - min] - 1] = arr[i]; count[arr[i] - min]--; } // Copiar el arreglo ordenado de vuelta al original for (int i = 0; i < arr.size(); i++) { arr[i] = output[i]; }}int main() { std::vector numbers = {2, 5, 3, 1, 4, 2, -2, 0}; std::cout << "Arreglo original: "; printVector(numbers); countingSort(numbers); std::cout << "Arreglo ordenado: "; printVector(numbers); // -2 0 1 2 2 3 4 5 return 0;}

Preguntas Frecuentes (FAQ)

¿Counting Sort es siempre mejor que Quick Sort?

No siempre. Counting Sort es superior (O(n+k)) solo cuando el rango de los datos (k) es pequeño y comparable al número de elementos (n). Quick Sort tiene una complejidad promedio de O(n log n) pero es mucho más versátil: funciona con cualquier tipo de dato comparable (no solo enteros), no requiere memoria adicional proporcional al rango de datos (es in-place) y suele ser más rápido en la práctica para datos con rangos grandes y distribuciones generales.

¿Qué pasa si no conozco el rango de los números?

Para usar Counting Sort, necesitas saber el rango para dimensionar el arreglo de conteo. Si no lo conoces de antemano, puedes hacer una pasada inicial por los datos para encontrar los valores mínimo y máximo. Esto añade un coste de O(n) al algoritmo, pero la complejidad total sigue siendo O(n+k).

¿Se puede usar Counting Sort para ordenar números negativos?

Sí, se puede adaptar fácilmente. Como se ve en el ejemplo de C++, la clave es encontrar el valor mínimo del arreglo y usarlo como un desplazamiento (offset). Al acceder al arreglo de conteo, en lugar de usar arr[i] como índice, se usa arr[i] - min. Esto mapea el rango de números (incluidos los negativos) a índices de arreglo válidos (de 0 en adelante).

¿Por qué es importante que Counting Sort sea estable?

La estabilidad es crucial cuando los elementos que se ordenan tienen datos asociados. Por ejemplo, si ordenas una lista de transacciones por fecha, y varias transacciones ocurrieron el mismo día, un ordenamiento estable preservará el orden original de esas transacciones. Además, es una propiedad indispensable para que algoritmos como Radix Sort, que utiliza un algoritmo de ordenación estable como subrutina, funcionen correctamente.