Contados
Movimentos
Contadores

  • A ser contado
  • Acabado de mover
  • No lugar

Mais sobre a ordenação por contagem

Ordenação por contagem

A ordenação por contagem funciona quando os valores são números inteiros num intervalo pequeno. Mantém um contador para cada valor possível, conta quantas vezes aparece cada um e, a partir dessas contagens, sabe exatamente onde fica cada valor. Veja os contadores a encher enquanto a lista é lida e depois a esvaziar à medida que cada valor passa para o seu bloco, um movimento de cada vez. Prima Reproduzir para ver a ordenação, ou Avançar e Recuar para ir um movimento de cada vez. Arraste a barra de passos para saltar para qualquer ponto. A faixa entre a lista e a linha do buffer tem um contador para cada valor. Os painéis mostram os valores contados, os movimentos e os contadores. Escolha quantas barras, como começam, ou escreva os seus próprios números. Com o quadro selecionado, as setas avançam e recuam, a barra de espaço reproduz e pausa, e Home e End saltam para o início e o fim.

Como funciona

  1. Escolha o número de barras e a ordem inicial, ou escreva os seus próprios números inteiros. Experimente uma lista com poucos valores distintos.
  2. Prima Reproduzir, ou use Avançar e Recuar para ir um valor de cada vez. Arraste a barra de passos para saltar para qualquer ponto da ordenação.
  3. Observe os contadores: enchem enquanto a lista é lida e depois descem à medida que cada valor é colocado.

Como funciona a ordenação por contagem

Crie um contador para cada valor, do menor ao maior. Leia a lista uma vez e some um ao contador de cada valor que encontrar. Depois some as contagens a partir do menor valor: o bloco de um valor começa logo a seguir a todos os valores menores. Por fim, percorra de novo a lista, mova cada valor para a próxima posição livre do seu bloco e copie o resultado de volta.

Rápida num intervalo pequeno

A ordenação por contagem lê a lista duas vezes e percorre os contadores uma vez, por isso o seu trabalho cresce com n + k: o número de valores mais o número de contadores. Com muitos valores num intervalo pequeno, como notas de exame de 0 a 100 ou idades, bate qualquer ordenação por comparação. Num intervalo grande, desperdiça tempo e memória em contadores que ninguém usa: três valores espalhados entre 1 e 1 000 000 precisariam de um milhão de contadores. É também o passo que a ordenação radix repete para cada dígito.

Perguntas frequentes

Como funciona a ordenação por contagem?

Conta quantas vezes aparece cada valor, soma as contagens para saber onde começa o bloco de cada valor e depois move cada valor diretamente para a próxima posição livre do seu bloco. Nunca compara dois valores.

Quando se deve usar a ordenação por contagem?

Quando os valores são números inteiros, ou podem ser convertidos em inteiros, e o intervalo do menor ao maior não é muito maior do que o número de valores: notas, idades, códigos pequenos. Nesse caso, demora um tempo proporcional a n + k.

A ordenação por contagem é estável?

Sim, quando os valores são movidos pela ordem da lista para a próxima posição livre do seu bloco, como aqui. É isso que permite à ordenação radix usá-la para cada dígito.

Porque não escrever simplesmente cada valor tantas vezes quantas foi contado?

Para números simples funciona, e é até mais simples. Mas os dados reais costumam ter mais do que a chave, como um nome com cada nota, e escrever as chaves contadas perderia essa informação. Mover os próprios elementos mantém tudo junto.

Os meus números são enviados para algum lado?

Não. A ordenação corre no seu navegador, e as suas últimas definições ficam no armazenamento local deste navegador.

Pronto para experimentar?

Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.

Ir para o editor