Dificuldade ★★☆
2 minutos de Leitura 🕒
O Counting Sort (Ordenação por Contagem) é um algoritmo de ordenação de inteiros criado por Harold Seward em 1954. Ele é um algoritmo de Programação Dinâmica, que funciona construindo um histograma cumulativo das chaves do arranjo de entrada e o usando essa estrutura para construir um arranjo de saída ordenado.
Apesar de possui um desempenho assintótico eficiente, o Counting Sort é geralmente usado como sub-rotina em outros métodos de ordenação não comparativos, como o Radix Sort e o Bucket Sort.
H de tamanho igual à maior chave presente no arranjo original A.A e armazene essa contagem no arranjo auxiliar H. Nesse arranjo auxiliar, a primeira posição dá a frequência de elementos de valor 0 em A, a segunda posição dá a frequência de elementos de valor 1 em A e assim por diante.H para criar o histograma cumulativo de cada elemento de A. Para tanto, acumule o valor da frequência do elemento i + 1 com a frequência do elemento i.H para construir um arranjo de saída ordenado. Para tanto, se x é um elemento no arranjo A que possui uma frequência cumulativa H(x), então x deve ser colocado no arranjo de saída entre a posição H(x) e H(x + 1).O desempenho do Counting Sort é pouco sensível a entrada. Por esse motivo, o desempenho assintótico do algoritmo é linear tanto para o pior quanto melhor caso. Se n é o número de elementos no arranjo de entrada e k é o valor da maior chave nesse arranjo, o desempenho do Counting Sort é:
O(n + k) operações inteirasVeja o código completo no GitHub.