Cuando su tarea de clasificación implica grandes conjuntos de pequeños enteros —como grados, edades o códigos categóricos— los algoritmos clásicos basados en comparación como QuickSort o MergeSort pueden sentirse exagerados. Estos algoritmos funcionan en el tiempo O(n log n) pero si la gama de posibles valores es limitada, puede ordenar el tiempo de uso de O(n + k) lineal con [FLT[0]

Cómo Contar Obras Clasificantes

Contando Sort explota el conocimiento de que los valores de entrada son enteros dibujados de una pequeña gama . En lugar de comparaciones de pares, construye un histograma de frecuencia de los valores y luego utiliza ese histograma para colocar cada elemento en su posición correcta clasificada.

El enfoque básico: reconstrucción directa

La versión más simple de Contando Sort funciona en dos pases:

  1. Frecuencias de bolsillo – Atraviese el array de entrada y aumente un contador para cada valor que vea.
  2. Overwrite the input] – Camine por el array de contador de menor a mayor y, por cada valor, escríbalo de nuevo en el array de entrada tantas veces como su cuenta.

Esto produce una salida ordenada pero no preservar el orden relativo de los duplicados (no es estable). La estabilidad importa cuando se clasifica en una clave mientras se mantiene el orden original de los registros con las teclas iguales. La variante estable, descrita a continuación, es la más utilizada en la práctica.

La variable estable: Conteos acumulativos

Para hacer Conteo Ordenar estable, añadimos un tercer paso:

  1. Cuenta las frecuencias como antes.
  2. Transformar el array de frecuencia en un array de conteo acumulativo. Después de este paso, contiene el número de elementos ≤ i].
  3. Ataque el array de entrada en reversa (de último elemento a primero). Para cada elemento, utilice su cuenta acumulativa para encontrar su posición en el array de salida, colocarlo, y decrementar el conteo.

Debido a que nos cruzamos en el revés, se conserva el orden relativo de elementos iguales. El array de salida está separado de la entrada, por lo que esta versión utiliza espacio adicional O(n) para la salida, mientras que la versión básica puede ordenar en el lugar por sobreescritura de la entrada.

Implementación de Conteos Clásicos en C#

A continuación se presentan dos implementaciones C#: la versión básica en el lugar (para escenarios donde la estabilidad es innecesaria) y la versión estable que utiliza un array auxiliar. Ambos requieren conocer el valor máximo por adelantado.

Básico (No estable) Contando Ordenar

Esta variante clasifica el array de entrada directamente sin un buffer de salida adicional. Es de memoria-eficiente pero no estable.

public static void CountingSortBasic(int[] array, int maxValue)
{
 int[] counts = new int[maxValue + 1];

 // Count each element's frequency
 for (int i = 0; i < array.Length; i++)
 {
 counts[array[i]]++;
 }

 // Overwrite the original array in sorted order
 int index = 0;
 for (int value = 0; value <= maxValue; value++)
 {
 while (counts[value]-- > 0)
 {
 array[index++] = value;
 }
 }
}

Stable Contando algo

La versión estable requiere un array de salida del mismo tamaño que la entrada. También utiliza los recuentos acumulativos para posicionar los elementos correctamente.

public static int[] CountingSortStable(int[] array, int maxValue)
{
 int[] counts = new int[maxValue + 1];
 int[] output = new int[array.Length];

 // Step 1: Count occurrences
 foreach (int num in array)
 {
 counts[num]++;
 }

 // Step 2: Transform counts to cumulative counts
 for (int i = 1; i <= maxValue; i++)
 {
 counts[i] += counts[i - 1];
 }

 // Step 3: Build the output array (iterate input in reverse for stability)
 for (int i = array.Length - 1; i >= 0; i--)
 {
 int value = array[i];
 output[counts[value] - 1] = value;
 counts[value]--;
 }

 return output;
}

En ambas implementaciones, es el entero más grande que aparece en el array. Si el verdadero máximo es desconocido, puede computarlo con un escaneo preparatorio (O(n)). La versión estable devuelve un nuevo array clasificado, dejando el original sin cambios.

Análisis de la complejidad

Que n] sea el número de elementos y k] = max – min + 1 (la gama de valores posibles).

  • Tiempo:] Contando Sort se ejecuta en O(n + k) tiempo. La fase de Conteo es O(n), el prefijo acumulativo es O(k), y la reconstrucción es O(n). Cuando k es O(n), el algoritmo es lineal.
  • Pace:] La versión básica utiliza el espacio extra O(k) para el array de conteo. La versión estable utiliza O(n + k) porque también asigna el array de salida. Esto hace que Conteo Sort sea inadecuado cuando el rango es grande en relación con el número de elementos.
  • Comparación con otras clases:] Comparación de tipos basados en comparación como QuickSort y MergeSort requieren al menos comparaciones de O(n log n). Para k pequeño (por ejemplo, k < 10,000 y n > 100.000), Contando Sort puede ser órdenes de magnitud más rápido.

Variaciones y extensiones

Manejo de los enteros negativos

Contando Ordenar funciona nativamente con números no negativos. Para manejar valores negativos, cambiar todo el rango por lo que el mínimo se convierte en cero. Por ejemplo, si los números van de -1000 a 1000, offset every element by +1000. El array de cuenta entonces tiene tamaño .

public static int[] CountingSortWithNegative(int[] array)
{
 if (array.Length == 0) return array;

 int min = array.Min();
 int max = array.Max();
 int range = max - min + 1;

 int[] counts = new int[range];
 int[] output = new int[array.Length];

 foreach (int num in array)
 counts[num - min]++;

 for (int i = 1; i < range; i++)
 counts[i] += counts[i - 1];

 for (int i = array.Length - 1; i >= 0; i--)
 {
 int value = array[i];
 output[counts[value - min] - 1] = value;
 counts[value - min]--;
 }

 return output;
}

Mapping Non-Integer Keys

Contando Sort requiere claves enteros. Si tus datos consisten en caracteres (bytes), o enumeraciones que pueden ser lanzados a enteros, puedes aplicarlo. Para objetos más grandes, puedes extraer una clave entero y ordenar los objetos en consecuencia, es exactamente cómo Radix Sort usa frecuentemente Contando Sort como su su subrutina interior.

Radix Sort Combo

Radix Sort procesa dígitos (o bits) individualmente, y Contando Sort es la opción natural para cada paso cuando la base (por ejemplo, 10 o 256) es pequeña. Esto permite ordenar a tiempo lineal de enteros arbitrarios, no sólo pequeños.

Consideraciones prácticas en C#

Pie de memoria y gran k

El mayor escollo es la asignación de un array de conteo más grande que la memoria disponible. Por ejemplo, clasificar 1.000 elementos con una gama de 1.000.000 de espacio de desperdicios. Siempre verificar que k] no es órdenes de magnitud más grande que n]—otros utilizan un tipo de comparación o un enfoque híbrido.

Paralelismo y Span implicalt;T

Para los arrays extremadamente grandes, puede paralelizar la fase de conteo partiendo la entrada a través de los hilos. Cada hilo cuenta su segmento en una matriz privada, y luego los resultados parciales se agregan. Utilizando y para el array de conteo puede reducir las asignaciones de montones cuando el rango es pequeño.

Casos de borde

  • Empleado] – volver inmediatamente.
  • Elemento único] – clasificar es trivial.
  • Todos los valores idénticos – el array de cuenta tiene una entrada no cero; la reconstrucción se ejecuta en O(n).
  • Profundidad de rango pero escasos datos] – Contando Sort se vuelve ineficiente porque la mayoría de las entradas son cero. Considere un enfoque de conteo basado en hash o Bucket Sort.

Recomendaciones sobre la ejecución

Uso Contando Ordenar cuando sepas que los enteros de entrada caen en una pequeña gama (por ejemplo, grados 0–100, edades 0–120, o códigos de error 0–255). Para mayores rangos, considera Radix Sort o un híbrido que se remonta a QuickSort para particiones de alto rango.

Cuando utilizar contando Ordenar (y cuando no hacerlo)

SituationRecommendation
Small integer range (k ~ n)Excellent choice – linear time, simple code.
Large integer range (k >> n)Avoid – memory waste and O(k) overhead.
Need stabilityUse the stable variant (cumulative counts).
Strings or objectsConsider Radix Sort or a comparison sort.
Extremely large datasetsCounting Sort can be parallelized; but watch memory.

Pautas y rendimiento

En un referente típico con n = 1.000.000 y k = 1.000, Contando Sort completa en aproximadamente 20–30% del tiempo tomado por (que utiliza introsort). La brecha se ensancha como k disminuye. A continuación se muestra una comparación aproximada (tiempos de ejecución en una CPU moderna con .NET 8):

n = 1,000,000 | k = 1,000
Array.Sort (QuickSort variant) : 68 ms
CountingSortBasic : 12 ms
CountingSortStable : 18 ms

Cuando el rango crece a 10.000, Contando Sort sigue ganando, pero el margen se estrecha. Para k = 100.000, la cabeza de memoria (contando 400 KB para el array de cuenta) comienza a dañar la caché de CPU, y el rendimiento puede degradarse.

Conclusión

Contando Sort es un algoritmo engañosamente simple que ofrece un rendimiento lineal cuando los datos se ajustan a sus limitaciones. Para los desarrolladores de C# que tratan con grandes arrays de pequeños enteros, es una herramienta valiosa que puede reducir drásticamente el tiempo de clasificación. Mantener un ojo en el rango de sus datos: si es pequeña y conocida, Contando Sort superará cualquier alternativa basada en comparación. Para clasificar más generalmente, use el dropli [F]

Para más lectura, consulte el Wikipedia artículo sobre Contando Sort, el ]Microsoft docs on Array.Sort[, y una guía práctica de ]GeeksforGeeks.