Radix Sort

Disponível somente no TrabalhosFeitos
  • Páginas : 3 (519 palavras )
  • Download(s) : 0
  • Publicado : 17 de maio de 2015
Ler documento completo
Amostra do texto
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. Emcompensaçã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 emvá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: chavescurtas
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 decaracteres 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 comcomprimento 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...