Ordenação radix
A ordenação radix é a exceção entre os algoritmos de ordenação: nunca pergunta qual de dois valores é maior. Lê os números algarismo a algarismo e ordena-os por um algarismo de cada vez, com dez baldes. A ideia é mais antiga do que os computadores: era assim que funcionavam as máquinas de ordenar cartões perfurados.
A ideia
Ordene os números apenas pelo algarismo das unidades. Depois ordene-os pelo algarismo das dezenas, mas de forma a manter os números com o mesmo algarismo das dezenas pela ordem que a primeira passagem lhes deu. Depois pelas centenas, da mesma forma. Após a última passagem, a lista está ordenada: as centenas decidem primeiro, os empates nas centenas já estão por ordem das dezenas, e os empates nas dezenas por ordem das unidades.
Uma passagem, com baldes
Cada passagem usa dez baldes, um para cada algarismo de 0 a 9. Percorra a lista do início ao fim e mova cada número para o balde do seu algarismo, atrás dos números que já lá estão. Depois esvazie os baldes de volta para a lista, por ordem, começando pelo balde 0. Mover os números pela ordem da lista e acrescentá-los ao fim de um balde é o que torna a passagem estável. A aplicação conta primeiro os números de cada algarismo, para que os baldes possam ficar lado a lado numa só linha, cada um a começar logo a seguir ao anterior: isso é uma ordenação por contagem sobre um algarismo.
Um exemplo
Pegue em 170, 45, 75, 90, 802, 24, 2, 66. Pelo algarismo das unidades: 170, 90, 802, 2, 24, 45, 75, 66. Pelo algarismo das dezenas: 802, 2, 24, 45, 66, 170, 75, 90; repare que 802 e 2, ambos com 0 nas dezenas, mantêm a ordem da primeira passagem. Pelo algarismo das centenas: 2, 24, 45, 66, 75, 90, 170, 802. Três passagens sobre oito números: 24 algarismos lidos e 48 movimentos, e nem uma comparação.
Quão rápida é?
Cada passagem lê um algarismo de cada número e move cada número duas vezes, por isso, para n números com d algarismos, o trabalho cresce com n · d. Uma ordenação por comparação precisa de pelo menos cerca de n log₂ n comparações no pior caso, porque tem de distinguir n! ordens possíveis com uma pergunta de sim ou não de cada vez. A ordenação radix não está sujeita a esse limite, pois nunca faz essas perguntas. Com muitas chaves curtas, como um milhão de números abaixo de 1000, três passagens são muito menos trabalho do que as cerca de 20 milhões de comparações de que uma ordenação por comparação precisaria. Com chaves longas ou poucos valores, a vantagem desaparece.
LSD e MSD, e história
A versão mostrada aqui começa pelo algarismo menos significativo (LSD). Ao contrário, começando pelo algarismo mais significativo (MSD), divide-se a lista em baldes pelo primeiro algarismo e ordena-se cada balde separadamente, o que se adequa a cadeias de comprimentos diferentes. A ordenação radix remonta às classificadoras de cartões perfurados que se seguiram às máquinas tabuladoras de Herman Hollerith para o censo dos EUA de 1890: uma classificadora deixava cair cada cartão numa de dez gavetas, conforme o furo numa coluna, e os operadores passavam o maço uma vez por coluna, começando pela última.
Experimente
Abra a aplicação e prima Avançar. Cada passagem conta primeiro os algarismos, o que delimita os baldes 0 a 9 na linha por baixo da lista. Depois os números caem um a um nos seus baldes, com o balde ativo destacado, e são copiados de volta. Escreva os seus próprios números até 999, como o exemplo acima, para ver as três passagens.
Perguntas frequentes
Qual é a complexidade temporal da ordenação radix?
O(n · d) para n chaves de d algarismos numa base fixa, mais o custo dos baldes em cada passagem. Precisa de O(n) de memória extra para o buffer onde ficam os baldes.
A ordenação radix é estável?
A ordenação radix LSD tem de ser: só funciona porque cada passagem mantém os valores com o mesmo algarismo pela ordem em que chegaram. Por isso, o resultado final também é estável.
A ordenação radix funciona com números negativos ou decimais?
Não diretamente, mas funciona com um truque: desloque os números negativos para que fiquem todos positivos, ou ordene-os à parte e inverta a sua ordem. Os números de vírgula flutuante podem ser ordenados pelos seus padrões de bits após uma pequena transformação.
Porquê a base 10?
Porque é fácil de acompanhar. Os computadores costumam ordenar 8 ou 16 bits de cada vez, por isso um número de 32 bits exige quatro ou duas passagens, com 256 ou 65 536 baldes.
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 radix