Algoritmo de ordenação Counting Sort

Algoritmo Counting Sort implementado em C#

Os algoritmos de ordenação mais conhecidos entre os programadores são os baseados em comparação. Para elucidar, algoritmos como o Merge Sort, Quick Sort, Bubble Sort e o Insertion Sort integram a lista das funções de classificação de elementos que se valem desse tipo de estratégia.

Entretanto, mesmo que em minoria, existem algoritmos que ordenam as estruturas de dados sem utilizar qualquer tipo de comparação entre os itens. O Counting Sort, apelidado em português de Ordenação de Contagem, encabeça o grupo dos algoritmos não baseados em comparação.

Conforme abordado no decorrer da publicação, o Counting Sort apresenta vantagens competitivas muito valiosas a partir do momento que traçamos um paralelo com os seus principais concorrentes. A sua complexidade de tempo se aproxima do nível linear, fator o qual lhe alça na posição de um dos mais velozes no ramo da ordenação, a depender sobretudo dos dados de entrada.

Entendendo o algoritmo

O entendimento da lógica operacional do Counting Sort envolve um estudo cuidadoso de seus quatro passos de execução. De acordo com o que foi destacado, este algoritmo ostenta uma técnica diferente para ordenar os elementos, fundamentada em chaves de acesso restritas a um intervalo específico.

Primeiro passo de execução do Counting Sort: encontrar o seu intervalo

A figura acima mostra justamente como o Counting Sort estabelece o limite de seu intervalo, etapa esta que caracteriza o início do seu processamento. Em linhas gerais, o algoritmo varre todos os números do array, buscando pelo maior elemento. Finalizada essa pesquisa simples, o Counting Sort passa a ter o seu intervalo de atuação definido.

Segundo passo de execução do Counting Sort: contar a quantidade de aparições dentro do intervalo

Continuando, a segunda fase do algoritmo se responsabiliza por contar a quantidade de aparições dos itens do vetor original. Para isso, o Counting Sort cria uma estrutura auxiliar, onde cada índice simboliza um número que faz parte do intervalo estipulado. 

De modo a exemplificar, o índice zero do array de contagem armazena o total de ocorrências do próprio número zero no vetor de entrada, enquanto o índice um contém o total de ocorrências do número um, e assim por diante.

Terceiro passo de execução do Counting Sort: modificar o array de contagem

Uma vez que os elementos foram devidamente contabilizados, o terceiro estágio do Counting Sort altera o vetor auxiliar. Essa modificação faz com que os índices da estrutura armazenem a soma das contagens anteriores. 

Ou seja, se no índice zero tínhamos duas aparições do número zero, e no índice um tínhamos três aparições do número um, o índice um passa a conter o resultado de cinco aparições. Prosseguindo, se o índice dois detinha hipoteticamente quatro aparições do número dois, este índice passa a conter o resultado de nove aparições.

Quarto passo de execução do Counting Sort: processar os dados de entrada

Por fim, o quarto passo do algoritmo processa os dados de entrada. Isso significa que o Counting Sort faz uma varredura pelos itens do vetor não ordenado, visando popular outro array auxiliar, identificado como output. Essa estrutura armazena os números de maneira ordenada. A posteriori, todos os seus elementos são copiados para o vetor original.

Contudo, para que o array output seja preenchido corretamente, o algoritmo aplica um procedimento engenhoso. No perpassar de cada iteração, o Counting Sort seleciona o número existente naquele determinado índice. Depois disso, o item obtido é utilizado como uma chave de acesso no array de contagem. 

Neste instante, através do vetor auxiliar em questão, o algoritmo encontra a posição que o número do vetor de entrada será inserido no vetor output. Perceba que a terceira etapa do Counting Sort alterou o array de contagem de tal forma que os valores em cada posição representassem o índice de saída dos elementos originais.

Após a inserção no vetor output, o Counting Sort decrementa o valor contido no índice acessado do array de contagem. Caso o vetor de entrada possua itens repetidos, essa instrução garante que estes números serão posicionados apropriadamente. 

Analisando a implementação do algoritmo

Para a surpresa de muitos, o Counting Sort supera a complexidade média de tempo dos algoritmos Quick Sort e Merge Sort. De acordo com os fundamentos da análise assintótica, o Counting Sort executa em O(N+M), onde N representa o tamanho do vetor de entrada, e M constitui o tamanho do vetor de contagem.

No que tange o uso do espaço auxiliar de memória, o Counting Sort novamente demonstra uma eficiência maior do que os seus pares. Assim como a sua complexidade de tempo, o algoritmo consome em média O(N+M) de memória, onde N reflete o tamanho do vetor de saída, e M configura o tamanho do vetor de contagem.

Em conformidade com as singularidades do Counting Sort, podemos afirmar que este ostenta uma performance que transcende os algoritmos de ordenação baseados em comparação. Contudo, essa vantagem de execução é constatada somente se o intervalo de processamento for da mesma ordem que os números do vetor de entrada.

Sendo assim, o Counting Sort engloba a lista dos algoritmos estáveis, que são aqueles que preservam a ordem dos elementos repetidos. Por outro lado, o Counting Sort está fora do grupo de algoritmos in-place, dado que a sua função exige a declaração de estruturas de dados auxiliares.

Enfim, cabe ressaltar que o Counting Sort opera de maneira extremamente ineficiente nas situações em que o intervalo de valores a serem classificados for muito grande. Portanto, dependendo da conjuntura, há a possibilidade deste algoritmo não ser recomendado, mesmo que sob o ponto de vista técnico ele tenha indicadores melhores.

Comparando o desempenho do algoritmo com o Merge Sort

Antecipado nos tópicos anteriores, o Counting Sort ultrapassa o desempenho do algoritmo Merge Sort. Enquanto o Counting Sort apresenta tanto uma complexidade de tempo, quanto um consumo do espaço auxiliar de memória de O(N+M), o Merge Sort fica para trás em ambos os critérios com O(NLogN).

Porém, vale relembrar que o Counting Sort demonstra efetivamente essa primazia na execução somente se o intervalo estipulado para o seu vetor de contagem não destoar da média dos elementos presentes no vetor de entrada. 

O quadro a seguir mostra um comparativo de execução entre os algoritmos Counting Sort e Merge Sort. Todas as informações foram geradas pela biblioteca BenchmarkDotNet. Compete frisar que para o input dos dados, os testes aplicados consideraram um dos melhores cenários possíveis para o Counting Sort.

Método	Input	Média de tempo	Espaço alocado
MétodoCountSort	InputInt32[10]	Média de tempo69.94 ns	Espaço alocado136 B
MétodoMergeSort	InputInt32[10]	Média de tempo207.22 ns	Espaço alocado624 B
MétodoCountSort	InputInt32[100]	Média de tempo582.54 ns	Espaço alocado856 B
MétodoMergeSort	InputInt32[100]	Média de tempo3,688.87 ns	Espaço alocado8000 B
MétodoCountSort	InputInt32[1000]	Média de tempo5,552.46 ns	Espaço alocado8056 B
MétodoMergeSort	InputInt32[1000]	Média de tempo37,605.10 ns	Espaço alocado92304 B
MétodoCountSort	InputInt32[10000]	Média de tempo59,967.30 ns	Espaço alocado80056 B
MétodoMergeSort	InputInt32[10000]	Média de tempo478,494.04 ns	Espaço alocado1072017 B
MétodoCountSort	InputInt32[100000]	Média de tempo841,646.91 ns	Espaço alocado800140 B
MétodoMergeSort	InputInt32[100000]	Média de tempo5,830,174.39 ns	Espaço alocado12031270 B

Logo de cara, tendo como base um vetor de dez elementos, o Counting Sort auferiu uma vantagem em detrimento do Merge Sort, processando com cerca de três vezes mais velocidade e utilizando quatro vezes menos espaço. A diferença se acentuou para cem itens, dado que o Counting Sort alcançou uma execução seis vezes mais rápida e alocou nove vezes menos memória.

Além disso, nos contextos em que o input assumiu a quantidade de mil, dez mil e cem mil elementos, o Counting Sort desempenhou seis, oito e sete vezes acima do Merge Sort no que diz respeito a média de tempo, respectivamente.

O código-fonte dos algoritmos e os detalhes extras acerca de seus respectivos desempenhos estão disponíveis no meu repositório do Github.