DAA - Radix Sort

Radix sorté um pequeno método que muitas pessoas usam intuitivamente ao colocar em ordem alfabética uma grande lista de nomes. Especificamente, a lista de nomes é primeiro classificada de acordo com a primeira letra de cada nome, ou seja, os nomes são organizados em 26 classes.

Intuitivamente, pode-se desejar classificar os números em seus dígitos mais significativos. No entanto, a classificação Radix funciona contra a intuição, classificando os dígitos menos significativos primeiro. Na primeira passagem, todos os números são classificados no dígito menos significativo e combinados em uma matriz. Em seguida, na segunda passagem, os números inteiros são classificados novamente nos segundos dígitos menos significativos e combinados em uma matriz e assim por diante.

Algorithm: Radix-Sort (list, n) 
shift = 1 
for loop = 1 to keysize do 
   for entry = 1 to n do 
      bucketnumber = (list[entry].key / shift) mod 10 
      append (bucket[bucketnumber], list[entry]) 
   list = combinebuckets() 
   shift = shift * 10

Análise

Cada tecla é examinada de uma só vez para cada dígito (ou letra, se as teclas forem alfabéticas) da tecla mais longa. Portanto, se a chave mais longa tiverm dígitos e há n chaves, radix sort tem ordem O(m.n).

No entanto, se olharmos para esses dois valores, o tamanho das chaves será relativamente pequeno quando comparado ao número de chaves. Por exemplo, se temos chaves de seis dígitos, podemos ter um milhão de registros diferentes.

Aqui, vemos que o tamanho das chaves não é significativo e este algoritmo é de complexidade linear O(n).

Exemplo

O exemplo a seguir mostra como a classificação Radix opera em sete números de 3 dígitos.

Entrada	1 r passagem	2 nd passagem	3 rd passagem
329	720	720	329
457	355	329	355
657	436	436	436
839	457	839	457
436	657	355	657
720	329	457	720
355	839	657	839

No exemplo acima, a primeira coluna é a entrada. As colunas restantes mostram a lista após classificações sucessivas na posição de dígitos cada vez mais significativos. O código para classificação Radix assume que cada elemento em uma matrizA do n elementos tem d dígitos, onde dígito 1 é o dígito de ordem mais baixa e d é o dígito de ordem mais alta.