balalbalbal

Radix Sorting
• Os registros a serem ordenados podem ter chaves bastante complexas, como por exemplo sequências de caracteres (lista telefônica) o Ordenação via comparação de chaves
• Várias aplicações têm chaves que são inteiros, definidos dentro de um intervalo
• Radix sorting: métodos que tiram proveito das propriedades digitais destes números o Chaves tratadas como números na base M (raiz ou radix) o Processamento e comparação de pedaços (bits) das chaves o Ex: ordenar faturas de cartão de crédito considerando pilhas com o mesmo dígito em cada posição. Neste caso M = 10

• Operação fundamental: dada um chave representada por um número binário a, extrair um conjunto contíguo de bits o Extrair os dois bits mais significativos de um número de 10 bits o Desloque (shift) os bits para a direita 8 posições, e faça um “and” bit-a-bit com a máscara 0000000011 o O shift elimina os bits à direita dos desejados e o and zera os bits a esquerda deles. Logo o resultado contém apenas os bits desejados.
• Pascal: operações shift e and são simuladas usando div e mod. o deslocar k bits de x para a direita: x div 2k o zerar todos os bits de ex exceto os j bits mais à direita: x mod 2j

• Radix sorting depende da função bits(x,j,k), que retorna os j bits que aparecem k bits à direita em x: o function bits(x, k, j : integer): integer o implementa (x div 2k ) mod 2j o implementação eficiente pre-computa (ou mantém como constantes) as potencies de 2.
• Radix sorting: idéia geral o Examine os bits das chaves um a um (ou em grupos), movendo as chaves com bits 0 para antes das chaves com bit 1 o Dois algoritmos: radix exchange e straight radix o Radix exchange sort: examina bits da esquerda para a direita
Œ Ordem relativa de duas chaves depende apenas do valor dos bits na posição mais significativa na qual eles diferem (primeira posição diferente da esquerda para a direita) o Straight radix sort: examina bits da direita para a
esquerda