Ordenação por contagem

Outra classe de algoritmos de ordenação é aquela na qual a definição da ordem se dá por contagem. O princípio básico é simples. Considere por exemplo uma coleção de elementos a ordenar onde as chaves podem assumir $N$ valores diferentes. Cria-se então uma tabela com $N$ contadores e varre-se a coleção do início ao fim, incrementando-se o contador correspondente à chave de valor $i$ cada vez que esse valor for encontrado. Ao final dessa varredura conhece-se exatamente quantas posições serão necessárias para cada valor de chave; os elementos são transferidos para as posições corretas na nova coleção, ordenada.

Claramente, a aplicação desse princípio básico de contagem a domínios com muitos valores tornaria-se inviável. Por exemplo, se os elementos são inteiros de 32 bits, o algoritmo de contagem básico precisaria de uma tabela com cerca de quatro bilhões ($2^{32}$) de contadores.

Radix sort é um algoritmo baseado neste conceito de ordenação por contagem que contorna este problema aplicando o princípio da ordenação por contagem a uma parte da representação do elemento, a raiz. O procedimento é repetido para a raiz seguinte até que toda a representação dos elementos tenha sido analisada. Por exemplo, a ordenação de chaves inteiras com 32 bits pode ser realizada em quatro passos usando uma raiz de oito bits, sendo que a tabela de contadores requer apenas 256 ($2^8$) entradas.

O procedimento para execução de radix sort é descrito no Algoritmo 2.6. Para essa descrição, assumiu-se que a chave da tabela são inteiros positivos, que serão analisados em blocos de $R$ bits a cada passo. As variáveis internas ao procedimento são pass, que controla o número de passos executados e também qual parte da chave está sendo analisada, iniciando pelos $R$ bits menos significativos; pos, que indica qual posição da tabela está sendo analisada; radixValue, o valor da parte da chave (entre 0 e $2^R-1$) no passo atual; count, a tabela de contadores; e $T_{\rm aux}$, uma cópia da tabela ordenada segundo a raiz sob análise ao final de cada passo.

O laço mais externo do algoritmo RADIXSORT (linhas 4 a 16) é repetido tantas vezes quantas forem necessárias para que a chave toda seja analisada em blocos de tamanho $R$ bits. Utiliza-se na linha 4 um operador SIZEOFBITS para determinar o tamanho da chave em bits.

O primeiro laço interno do algoritmo (linhas 5 e 6) simplesmente inicializa o arranjo de contadores, pois este será reutilizado em todos os demais passos do laço. No laço seguinte (linhas 7 a 9), a tabela é percorrida para avaliar o valor da raiz em cada posição (linha 8) e assim atualizar a contagem de valores (linha 9). Na seqüência (linhas 10 e 11), gera-se a soma acumulada de contadores, o que permite avaliar quantas chaves com raiz de valor menor que o indicado existem na tabela. Essa informação permitirá que, no próximo laço (linhas 12 a 15), a tabela $T_{\rm aux}$ seja preenchida colocando cada entrada da tabela $T$ na nova posição que lhe corresponde segundo esse valor de raiz; cada vez que uma entrada é colocada na tabela, o valor do contador associado deve ser decrementado (linha 15) para que a próxima raiz com o mesmo valor seja colocada na posição correta, anterior à última ocupada. Finalmente, a tabela $T$ recebe a tabela ordenada segundo a raiz e o procedimento é repetido para o bloco de bits seguinte da chave. Após a varredura do último bloco (o mais significativo), a tabela estará completamente ordenada.

Radix sort é um algoritmo rápido, mas apresenta como principal desvantagem a necessidade de espaço adicional de memória -- uma área do mesmo tamanho ocupado pelo conjunto de elementos sendo ordenado é necessária para receber os dados re-ordenados após cada contagem. Quando o espaço de memória não é um recurso limitante, radix sort é um algoritmo atrativo, com complexidade temporal linear $O(n)$.