- Balde em uso
- Acabado de mover
- Copiados de volta
- No lugar
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
- 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.
- 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.
- 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