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.

Barras de uma lista, uma faixa de contadores que mostra quantas vezes aparece cada valor e uma linha de buffer onde cada valor tem o seu próprio bloco
Barras de uma lista, uma faixa de contadores que mostra quantas vezes aparece cada valor e uma linha de buffer onde cada valor tem o seu próprio bloco

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