Quando sua tarefa de ordenação envolve grandes arrays de pequenos inteiros, como graus, idades ou códigos categóricos, os algoritmos clássicos baseados em comparação, como QuickSort ou MergeSort, podem parecer um exagero. Estes algoritmos são executados em tempo O(n log n), mas se o intervalo de valores possíveis for limitado, você pode classificar em O(n + k) linear com Contando Ordenar[]. Este algoritmo de ordenação não- comparada aproveita o fato de que você pode contar ocorrências em vez de comparar elementos, fornecendo um tipo estável que é simples e rapidamente para as entradas certas.

Como Funciona a Contagem de Ordenação

A contagem Ordenar explora o conhecimento de que os valores de entrada são inteiros desenhados a partir de um pequeno intervalo . Em vez de comparações emparelhadas, ele constrói um histograma de frequência dos valores e usa esse histograma para colocar cada elemento na sua posição ordenada correta.

A abordagem básica: reconstrução direta

A versão mais simples de Contagem Ordenar funciona em dois passes:

  1. Contar frequências – Iterar através do array de entrada e incrementar um contador para cada valor que você vê.
  2. Sobrescrever a entrada – Passe pelo array de contador do menor ao maior e, para cada valor, escreva-o de volta no array de entrada tantas vezes quanto sua contagem.

Isto produz uma saída ordenada, mas não preserva a ordem relativa das duplicatas (não é estável). A estabilidade importa quando você classifica em uma tecla, mantendo a ordem original dos registros com teclas iguais. A variante estável, descrita a seguir, é a mais usada na prática.

A Variante Estável: Contagem Cumulativa

Para tornar a Contagem estável, adicionamos uma terceira passagem:

  1. Contar frequências como antes.
  2. Transforme o array de frequência em um array de contagem cumulativa. Após esta etapa, detém o número de elementos ≤ i.
  3. Iterar o array de entrada ao contrário (do último elemento ao primeiro). Para cada elemento, use sua contagem cumulativa para encontrar sua posição no array de saída, colocá-lo e diminuir a contagem.

Como atravessamos ao contrário, a ordem relativa de elementos iguais é preservada. O array de saída é separado da entrada, então esta versão usa O(n) espaço adicional para a saída, enquanto a versão básica pode ordenar no lugar, sobrepondo a entrada.

A implementar a classificação em C#

Abaixo estão duas implementações C#: a versão básica no local (para cenários onde a estabilidade é desnecessária) e a versão estável que usa um array auxiliar. Ambos requerem saber o valor máximo com antecedência.

Classificação básica (não- estável)

Esta variante classifica o array de entrada diretamente sem um buffer de saída extra. É eficiente em memória, mas não estável.

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;
 }
 }
}

Ordenação de contagem estável

A versão estável requer uma matriz de saída do mesmo tamanho que a entrada. Ela também usa contagens cumulativas para posicionar os elementos corretamente.

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;
}

Em ambas as implementações, é o maior inteiro que aparece no array. Se o máximo verdadeiro for desconhecido, você pode computá- lo com uma varredura preparatória (O(n)). A versão estável retorna um novo array ordenado, deixando o original inalterado.

Análise de Complexidade

Seja n o número de elementos e k = max – min + 1 (a gama de valores possíveis).

  • [[FLT: 0]] Tempo: [[FLT: 1]] A contagem Ordenar é executada em [[FLT: 2]] O( n + k) [[FLT: 3]] tempo. A fase de contagem é O( n), o prefixo cumulativo é O( k), e a reconstrução é O( n). Quando k é O( n), o algoritmo é linear.
  • [[FLT: 0]]Espaço: A versão básica usa O( k) espaço extra para o array de contagem. A versão estável usa O( n + k) porque também aloca o array de saída. Isto torna a Contagem Ordenar inadequado quando o intervalo é grande em relação ao número de itens.
  • [[ FLT: 0]] Comparação com outros tipos: [[ FLT: 1]] Tipos baseados em comparação como QuickSort e MergeSort requerem pelo menos comparações O( n log n). Para k pequeno (por exemplo, k < 10.000 e n & gt; 100.000), a contagem Ordenar pode ser mais rápida.

Variações e extensões

Manuseamento de Inteiros Negativos

A contagem Ordenar funciona nativamente com inteiros não- negativos. Para lidar com valores negativos, mude todo o intervalo para que o mínimo se torne zero. Por exemplo, se os números variam de - 1000 a 1000, offset cada elemento em +1000. O array de contagem então tem tamanho .

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;
}

Mapeamento de chaves não integradas

A contagem Ordenar requer chaves inteiras. Se os seus dados consistirem em caracteres (bytes), ou enumerações que possam ser fundidas em inteiros, você ainda poderá aplicá- lo. Para objetos maiores, você poderá extrair uma chave inteira e ordenar os objetos de acordo -- é exatamente assim que o Radix Ordenar usa frequentemente a Contagem Ordenar como sua sub- rotina interna.

Combinação de Ordenação de Radix

Radix Sort processa os dígitos (ou bits) individualmente, e Contar Ordenar é a escolha natural para cada passagem quando a base (por exemplo, 10 ou 256) é pequena. Isto permite a ordenação linear- time de inteiros arbitrários, não apenas pequenos.

Considerações Práticas em C#

Pegada de memória e grande k

A maior armadilha é alocar uma matriz de contagem maior do que a memória disponível. Por exemplo, ordenar 1.000 elementos com uma faixa de 1.000.000 de espaços de desperdícios. Sempre verifique se k não é ordem de magnitude maior do que n—ou então use uma classificação de comparação ou uma abordagem híbrida.

Paralelismo e Span<T>

Para arrays extremamente grandes, você pode paralelizar a fase de contagem dividindo a entrada entre threads. Cada thread conta seu segmento em um array privado, e então os resultados parciais são agregados. Usando e para o array de contagem pode reduzir alocação de heap quando o intervalo é pequeno.

Casos de borda

  • Array vazio – retornar imediatamente.
  • Elemento único – a ordenação é trivial.
  • Todos os valores idênticos – o array de contagem tem uma entrada não-zero; a reconstrução é executada em O(n).
  • Grande alcance, mas dados esparsos – Contar Ordenar torna-se ineficiente porque a maioria das entradas de contagem são zero. Considere uma abordagem de contagem baseada em hash ou Bucket Sort.

Recomendações de desempenho

Usar Contagem Ordenar quando você sabe que os inteiros de entrada caem em um pequeno intervalo (por exemplo, graus 0–100, idades 0–120, ou códigos de erro 0–255). Para intervalos maiores, considere Radix Sort ou um híbrido que cai de volta para QuickSort para partições de alto alcance.

Quando usar a classificação (e quando não usar)

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.

Marcação de benchmarking e desempenho

Num valor de referência típico com n = 1.000.000 e k = 1.000, a Contagem Ordenar completa em cerca de 20-30% do tempo tomado por (que usa introsorte). A diferença aumenta à medida que o k diminui. Abaixo está uma comparação aproximada (tempos de execução numa CPU moderna com .NET 8):

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

Quando o intervalo cresce para 10.000, Contando Ordenar ainda ganha, mas a margem estreita. Para k = 100.000, a sobrecarga de memória (em 400 KB para o array de contagem) começa a prejudicar cache de CPU, e o desempenho pode degradar.

Conclusão

Contar Ordenar é um algoritmo enganosamente simples que oferece desempenho linear quando os dados se encaixam nas suas restrições. Para os desenvolvedores de C# que lidam com grandes arrays de pequenos inteiros, é uma ferramenta valiosa que pode reduzir drasticamente o tempo de ordenação. Mantenha um olho no intervalo de seus dados: se for pequeno e conhecido, Contar Ordenar superará qualquer alternativa baseada em comparação. Para uma ordenação mais geral, use o built-in , mas sempre esteja pronto para cair em Contar Ordenar quando os números se alinharem — literalmente e figurativamente.

Para mais informações, consulte o artigo Wikipedia sobre Contagem Ordenada, o Docs Microsoft sobre Array.Sort, e um guia prático de GeeksforGeeks.