Algarismos lidos
Movimentos
Passagem

  • Balde em uso
  • Acabado de mover
  • Copiados de volta
  • No lugar

Mais sobre a ordenação radix

Ordenação radix

A ordenação radix ordena números inteiros sem nunca comparar dois deles. Ordena a lista pelo algarismo das unidades, depois pelo das dezenas, depois pelo das centenas, movendo de cada vez os valores para dez baldes e copiando-os de volta por ordem. Veja os baldes encherem na linha por baixo da lista, um movimento de cada vez, e a lista ficar ordenada por cada vez mais algarismos. 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. Os baldes 0 a 9 ficam lado a lado na linha por baixo da lista. Os contadores mostram algarismos lidos, movimentos e passagens. Escolha quantas barras, como começam, ou escreva os seus próprios números até 999. 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 até 999 para ver a passagem das centenas.
  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. Acompanhe cada passagem: contar os algarismos, mover cada valor para o seu balde e depois copiar os baldes de volta.

Como funciona a ordenação radix

Olhe apenas para o último algarismo de cada número e ordene a lista por ele: coloque cada número num de dez baldes, de 0 a 9, pela ordem em que chegam, e depois copie os baldes de volta, um após o outro. Faça o mesmo com o algarismo das dezenas e depois com o das centenas. Como cada passagem mantém a ordem dos números que partilham um algarismo, as passagens anteriores continuam a decidir a ordem entre eles e, após a última passagem, toda a lista está ordenada.

Nenhuma comparação

As ordenações por comparação precisam de pelo menos cerca de n log₂ n comparações no pior caso, seja qual for o truque que usem. A ordenação radix contorna esse limite lendo algarismos: cada passagem lê um algarismo de cada valor e move cada valor duas vezes, por isso d algarismos exigem d passagens e o trabalho cresce com n · d. Para listas longas de chaves curtas, compensa: um milhão de números até 999 exige três passagens, onde uma ordenação por comparação precisa de cerca de 20 milhões de comparações. O preço é que só funciona com chaves feitas de algarismos ou caracteres, e precisa de espaço para os baldes.

Perguntas frequentes

Como funciona a ordenação radix?

Ordena os números pelo último algarismo, depois pelo algarismo anterior, e assim por diante até ao primeiro. Cada passagem distribui os números por dez baldes segundo esse algarismo, mantendo a ordem, e copia os baldes de volta. Após a passagem do algarismo mais significativo, a lista está ordenada.

Porquê começar pelo último algarismo?

Porque cada passagem é estável: os números com o mesmo algarismo mantêm a ordem que as passagens anteriores lhes deram. Assim, a última passagem, sobre o primeiro algarismo, decide a ordem, e os empates são desfeitos pelos algarismos já ordenados. Chama-se ordenação radix LSD (least significant digit, algarismo menos significativo).

A ordenação radix é mais rápida do que o quicksort?

Pode ser, com muitas chaves curtas: o seu trabalho cresce com o número de valores vezes o número de algarismos, sem n log n. Com poucos valores, chaves muito longas ou dados que não são feitos de algarismos, o quicksort e o merge sort são normalmente mais rápidos e mais simples.

Qual é a relação com a ordenação por contagem?

Cada passagem da ordenação radix é uma ordenação por contagem sobre um algarismo: contar quantos valores têm cada algarismo, calcular onde começa cada balde e mover os valores para lá por ordem.

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