Introdução à Contagem Ordenar

A classificação de contagem é um algoritmo de ordenação não- comparado que se sobressai ao ordenar inteiros sobre um intervalo pequeno e conhecido. Ao contrário dos tipos baseados em comparação, como o Quicksort ou o Mergesort, que dependem de comparações de elementos emparelhados, a contagem de ordenação determina a ordem ordenada, contando a frequência de cada valor distinto. Esta abordagem produz complexidade de tempo linear em condições favoráveis, tornando- a uma opção para muitas aplicações críticas ao desempenho, onde o domínio de entrada é limitado.

O algoritmo foi descrito pela primeira vez por Harold H. Seward em 1954 e continua a ser uma técnica fundamental na ciência da computação. A sua simplicidade e eficiência tornam- no ideal para tarefas como ordenar idades de estudantes, notas ou qualquer dado inteiro com um modesto spread. Ao alavancar o armazenamento auxiliar proporcional ao intervalo de valores, a Contagem Ordenar evita o limite inferior de ordenação de comparação O(n log n), atingindo o tempo O(n + k) em que k é o intervalo de valores de entrada.

Como Funciona a Contagem de Ordenação

O mecanismo de núcleo de Contagem Ordenada é simples: conta quantas vezes cada valor aparece no array de entrada, então usa essa contagem para calcular a posição final de cada elemento. O processo consiste em três fases distintas:

  1. Contagem: Criar uma matriz de contagem de tamanho k (a gama de valores de entrada), inicializada para zero. Iterar através do array de entrada e incrementar a contagem para cada valor.
  2. Computando prefixos: Transformar o array de contagem em um array de soma de prefixos, onde cada elemento no índice i detém a contagem cumulativa de elementos menor ou igual a i. Esta etapa determina as posições de partida para cada valor distinto na saída ordenada.
  3. Elementos de colocação: Cruzar o array de entrada da direita para a esquerda (para estabilidade), usar o array de contagem para encontrar o índice correto no array de saída, colocar o elemento lá, e diminuir a contagem. O resultado final é uma cópia ordenada da entrada.

O algoritmo retorna um novo array ordenado, deixando o original inalterado. Uma variante chamada no local Contagem Ordenar existe mas raramente é usada porque compromete a estabilidade ou a eficiência do espaço.

Exemplo passo a passo

Considere ordenar o array [4, 2, 8, 3, 3] onde os valores variam de 0 a 8.

  1. Contagem: Contagem tamanho 9 (0–8) → [0,1,2,2,1,0,0,0,01]. (Índice 1 aparece uma vez, índice 2 duas vezes, índice 3 duas vezes, índice 4 uma vez, índice 8 uma vez.)
  2. Impressões prefixas: Transformar para cumulativo → [0,1,3,5,6,6,6,6,7]. Agora cada valor nos diz a posição inicial para esse número em resultado ordenado.
  3. Saída: Traverse original array from end: first element read is 1 → position = count[1] - 1 = 0 → output[0]=1, contagem de decrementos[1] to 0. Em seguida, é 3 → position = count[3] - 1 = 4 → output[4]=3, count[3]=4. Continue até todos os elementos colocados. Saída final: [1,2,2,3,3,4,8].

Este exemplo demonstra como Contar Ordenar evita comparações inteiramente, dependendo apenas de operações aritméticas.

Complexidade computacional

Complexidade do Tempo

  • Melhor, Média e Pior Caso: O(n + k), onde n é o número de elementos e k é o intervalo de valores de entrada. Quando k é pequeno em relação a n, o algoritmo é executado em tempo linear.
  • [[FLT: 0]] Comparação com os tipos de comparação:[[FLT: 1]] O Quicksort e o Mergesort têm complexidade média de O( n log n). Para n = 106 e k = 1000, Contar Ordenar (□ 1, 001.000 operações) é cerca de 13 vezes mais rápido do que um tipo típico de O( n log n).

Complexidade do Espaço

  • [[FLT: 0]]Primário: O( k) para o array de contagem, mais O( n) para o array de saída. Esta sobrecarga de memória pode ser proibitiva se k for grande (por exemplo, ordenar inteiros de 32 bits onde k = 232).
  • Variante estável: Requer uma matriz auxiliar de saída de tamanho n; variantes no local sacrificam estabilidade ou usam manipulação de índice complexa.

Quando Usar a Ordenação de Contagem

Contagem Ordenar é mais eficaz nas seguintes condições:

  • A entrada consiste em inteiros (ou dados que podem ser mapeados para uma pequena faixa inteira, como caracteres ou categorias discretas).
  • O intervalo k não é significativamente maior do que n. Uma regra comum de polegar é k ≤ O(n).
  • A memória não é severamente restrita, porque o array de contagem e buffer de saída requerem espaço extra.
  • É necessária estabilidade (por exemplo, ordenação por várias teclas). A implementação padrão é estável quando os elementos são colocados da direita para a esquerda.

Casos de excelente utilização incluem classes de classificação (0–100), idades (0–120), categorias de produtos (até algumas centenas de SKUs), ou como subrotina em Radix Sort[].

Limitações e Considerações

Apesar de sua velocidade, Contar Sort tem desvantagens que limitam sua aplicabilidade:

  • Integer only: Não pode ordenar diretamente números de pontos flutuantes ou strings a menos que sejam convertidos para um conjunto inteiro contíguo.
  • Grande intervalo: Se k anãs n - por exemplo, ordenar 100 números com valores entre 1 e 107 - o array de contagem consome memória enorme enquanto classifica apenas alguns elementos.
  • Não-adaptativo: Contar Ordenar requer sempre a digitalização de toda a entrada e a construção do array de contagem, mesmo que os dados já estejam ordenados ou quase ordenados.
  • Valores negativos: O Standard Counting Sort assume números inteiros não negativos. Para lidar com os negativos, você pode deslocar os valores subtraindo o mínimo (fazendo o intervalo 0 ao máximo – min).

Essas limitações significam que Contar Sort é uma ferramenta especializada, não uma substituição universal para algoritmos de finalidade geral.

Comparação com Algoritmos de Ordenação Relacionados

Contando Ordenação vs. Ordenação Radix

O Radix Sort estende a ideia, separando dígitos de menos significativo para mais significativo, usando uma ordenação estável (muitas vezes Contando Ordenar) em cada dígito. Enquanto a Contagem Ordenar funciona em uma passagem sobre o intervalo completo k, o Radix Sort executa várias passagens sobre um intervalo de dígitos menor (por exemplo, base 256), reduzindo o uso de memória para k grande. Por exemplo, ordenar inteiros de 32 bits com Contar Ordenar necessitaria de uma matriz de 232 entradas, enquanto que o Radix Ordenar com dígitos de 8 bits requer 256 entradas por passo e apenas quatro passagens.

Contando Ordenar vs. Bucket Ordenar

O Bucket Sort distribui elementos em vários baldes e ordena cada balde individualmente (muitas vezes com a classificação de inserção). A contagem Ordenar pode ser vista como um caso especial de Bucket Sort, onde cada balde corresponde a um único valor distinto. O Bucket Sort funciona bem em dados de pontos flutuantes distribuídos uniformemente, mas a contagem Ordenar é limitada a domínios inteiros.

Implementação de uma classificação de contagem estável

A estabilidade é importante ao ordenar por uma tecla, preservando a ordem relativa de elementos iguais de outra chave. O algoritmo padrão de ordenação de contagem é inerentemente estável quando o circuito de posicionamento de saída atravessa a entrada da direita para a esquerda. Aqui está um esboço textual da variante estável:

  1. Calcular o array de contagem como descrito.
  2. Converter para prefixos (posições de cada valor na saída ordenada).
  3. Iterar o array de entrada em ordem reversa. Para cada elemento, coloque-o na posição indicada pela sua contagem, em seguida, decremente que contagem.

Como processamos elementos do fim, a última ocorrência de um dado valor entra no índice mais alto possível, preservando a ordem relativa. Esta versão estável é essencial para que o Radix Ordene funcione corretamente em cada dígito.

Aplicações Práticas

  • Sistemas de classificação educacional:] Ordenar centenas de pontuações (intervalo 0–100) em tempo O(n).
  • Bioinformática: Ordenação de contagens de leitura inteiras ou frequências k-mer de DNA quando o tamanho do alfabeto é pequeno (A, C, G, T).
  • Manutenção do índice de base de dados: Ordenar identificadores inteiros únicos no intervalo suficientemente pequeno para caber na memória.
  • Processamento de imagens: Ordenar caixas de histogramas ou intensidades de cor (0–255) ao construir tabelas de pesquisa.
  • Sortir por chave secundária: Usado dentro do Radix Sort, que é o cavalo de trabalho para uma classificação eficiente em muitas bibliotecas e linguagens (por exemplo, o .NET runtime usa uma mistura adaptativa de algoritmos, incluindo Contagem Ordenar para pequenas faixas).

Para mais informações sobre a teoria e variantes, consulte referências autoritárias como Wikipedia: Counting Sort e GeeksforGeeks: Counting Sort. Comparações práticas com outros algoritmos podem ser encontradas em Brilliant’s Counting Sort article.

Otimizando a classificação de contagem para grandes intervalos

Quando k é grande, mas n também é grande, Contar Sort puro torna-se memória-intensiva. Existem várias otimizações:

  • Esparte de compressão: Use um mapa de hash em vez de um array contíguo quando a faixa de valores usados é grande, mas o número de valores distintos é pequeno. Isto negocia indexação de tempo constante para hashing overhead, mas reduz o consumo de memória.
  • Abordagens híbridas: Combine Contagem Ordenar com outros algoritmos. Por exemplo, se o intervalo exceder 106, use Radix Ordenar com uma base que mantenha intervalos de dígitos pequenos.
  • Vantagens no lugar: Algumas otimizações reduzem o espaço extra para O(k) sem um array de saída, mas geralmente sacrificam estabilidade ou exigem ciclos para localizar posições.

Conclusão

A contagem Ordenar destaca- se como um algoritmo notavelmente eficiente para a ordenação de inteiros quando o intervalo de valores é pequeno em relação ao número de elementos. A sua complexidade de tempo e desempenho linear O(n + k) torna- o indispensável em cenários como a ordenação de graus, sub- rotinas de ordenação de Radix e aplicações com chaves inteiras delimitadas. Contudo, a dependência do algoritmo em entradas inteiras e a sua memória em excesso para grandes intervalos recorda- nos que nenhum tipo único é ideal para todas as situações. Ao compreender quando a contagem de Ordenar se destaca - e quando falha - os desenvolvedores podem construir sistemas mais rápidos e previsíveis. Para mais leitura sobre ordenação baseada em não- comparação, veja [[FLT: 0]] TutorialsPoint: Contando Ordenar [[FLT: 1]] e [[FLT: 2]Coursera: Contando Ordenar a Lectura[[FLT: 3]].