Radix Sort

Radix Sort
Algoritmo de ordenação

Radix Sort




O Radix Sort é um algoritmo de ordenação por contagem rápido e estável, que pode ser usado para ordenar itens que estão identificados por chaves únicas.
Cada chave é uma cadeia de caracteres(lista telefônica) ou número, e o radix sort ordena estas chaves numa qualquer ordem relacionada com a lexicografia.



Em muitas aplicações em que é necessário velocidade, o radix sort melhora as ordenações por comparação, como heapsort e o mergesort, que necessitam de Ω(n · log n) comparações, onde “n” é o número de itens a serem ordenados. Em compensação, algoritmos de ordenação baseados em comparações oferecem flexibilidade por serem aptos a ordenar de outras formas que não a lexicográfica. No entanto, essa habilidade é de pouca importância em várias aplicações práticas. Classificações


Existem duas classificações para o
Radix Sort:
› Least significant digit (LSD – Dígito menos

significativo) radix sort;
› Most significant digit (MSD – Dígito mais significativo) radix sort.

Least significant digit (LSD)


O radix sort LSD começa do dígito menos significativo até o mais significativo, ordenando tipicamente da seguinte forma: chaves curtas vem antes de chaves longas, e chaves de mesmo tamanho são ordenadas lexicograficamente. Isso coincide com a ordem normal de representação dos inteiros, como a seqüência "1, 2, 3, 4, 5, 6, 7,
8, 9, 10". Os valores processados pelo algoritmo de ordenação são frequentemente chamados de
“chaves”, que podem existir por si próprias ou associadas a outros dados. As chaves podem ser strings de caracteres ou números.

LSD


O radix sort LSD opera na notação Big O, em
O(nk), onde "n" é o número de chaves, e "k" é o comprimento médio da chave. É possível garantir esse desempenho para chaves com comprimento variável agrupando todas as chaves que tem o mesmo comprimento e ordenando separadamente cada grupo de chaves, do mais curto para o mais comprido, de modo a evitar o processamento de