Ordenação por contagem
A ordenação por contagem não ordena comparando valores. Se souber que cada valor é um número inteiro entre, digamos, 1 e 40, pode simplesmente contar quantos há de cada um e, a partir das contagens, saber onde fica cada um. Num intervalo pequeno, ordenar dificilmente pode ser mais rápido.
Contar
Encontre o menor e o maior valor e crie um contador para cada valor entre eles, todos a começar em zero. Leia a lista uma vez do início ao fim e some um ao contador de cada valor que encontrar. Os contadores formam agora um histograma: quantos 1, quantos 2, e assim por diante. Com n valores e k contadores, isto leva n passos.
Somar
Os valores iguais ao menor valor vêm primeiro, por isso o seu bloco começa na posição 1. O bloco do valor seguinte começa logo a seguir, e assim por diante: cada bloco começa depois da soma de todas as contagens anteriores. Estes totais acumulados, chamados somas de prefixos, transformam o histograma num mapa da lista ordenada. Isto leva k passos.
Colocar
Leia a lista uma segunda vez e mova cada valor para a próxima posição livre do seu bloco. Como os valores são movidos pela ordem em que aparecem, os valores iguais mantêm a sua ordem original: a ordenação por contagem é estável. Copie o buffer de volta e a lista fica ordenada. A aplicação mostra cada contador a descer à medida que os seus valores são colocados.
Um exemplo
Pegue em 4, 1, 3, 4, 2, 1, 4. Os contadores de 1 a 4 terminam em 2, 1, 1 e 3. Somando, obtêm-se os blocos: os 1 nas posições 1 e 2, o 2 na posição 3, o 3 na posição 4 e os 4 nas posições 5 a 7. Colocar os valores pela ordem da lista dá 1, 1, 2, 3, 4, 4, 4: 7 valores contados, 14 movimentos, 4 contadores e nenhuma comparação.
Quando usar
O trabalho total cresce com n + k. Quando k é pequeno em comparação com n, como mil notas de exame de 0 a 100, a ordenação por contagem é mais rápida do que qualquer ordenação por comparação, que precisa de cerca de n log₂ n comparações. Quando o intervalo é grande, é um desperdício: alguns valores espalhados até um milhão precisam de um milhão de contadores. A ordenação radix resolve isso aplicando a ordenação por contagem uma vez por dígito, por isso cada passagem só precisa de dez contadores. Harold Seward descreveu a ordenação por contagem, juntamente com a ordenação radix, em 1954.
Explore
Abra a aplicação e prima Avançar. A faixa entre a lista e a linha do buffer mostra um contador por valor. Veja os contadores a encher enquanto a lista é lida, os blocos a aparecer no buffer quando as contagens são somadas e os contadores a descer à medida que os valores são colocados. Escolha poucos valores distintos para ver blocos grandes, ou escreva números muito afastados para ver quantos contadores um intervalo grande exige.
Perguntas frequentes
Qual é a complexidade temporal da ordenação por contagem?
O(n + k) para n valores e k valores possíveis, e O(n + k) de memória extra para os contadores e o buffer.
Porque é que a ordenação por contagem nem sempre é a mais rápida?
Porque o seu custo depende do intervalo dos valores, e não só de quantos são. Se o intervalo for muito maior do que a lista, a maioria dos contadores fica a zero e o tempo e a memória são desperdiçados.
A ordenação por contagem lida com números negativos?
Sim. Os contadores vão do menor ao maior valor, por isso subtraia o menor valor para obter o índice de um contador. A aplicação faz o mesmo.
A ordenação por contagem é estável?
Sim, desde que os valores sejam movidos pela ordem da lista para a próxima posição livre do seu bloco. A ordenação radix depende disso.
Pronto para experimentar?
Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.
Experimentar a ordenação por contagem