Radix

CIESA
Ciência da Computação
Projeto e Análise de Algoritmos

Radix Sort

Alunos: Édilo Sousa da Silva
Edivam da Silva
Maikon Santos
Romário David

Conceito
O algoritmo de ordenação radix foi originalmente usado para ordenar cartões perfurados. Um algoritmo computacional para o radix sort foi inventado em 1954 no MIT por Harold H.
Seward.
O Radix sort é um algoritmo de ordenação 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 ou número, e o radix sort ordena estas chaves numa qualquer ordem relacionada com a lexicografia.

Como Funciona?
Existem duas classificações do radix sort, que são: Least significant digit (LSD – Dígito menos significativo) radix sort; - Most significant digit (MSD – Dígito mais significativo) radix sort.
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.

Como Funciona?
Já o radix sort MSD trabalha no sentido contrário, usando sempre a ordem lexicográfica, que é adequada para ordenação de strings, como palavras, ou representações de inteiros com tamanho fixo. A seqüência "b, c, d, e, f, g, h, i, j, ba" será ordenada lexicograficamente como "b, ba, c, d, e, f, g, h, i, j". Se essa ordenação for usada para ordenar representações de inteiros com tamanho variável, então a representação dos números inteiros de 1 a 10 terá a saída
"1, 10, 2, 3, 4, 5, 6, 7, 8, 9".

Vantagens
Em muitas aplicações em que é necessário velocidade, o radix sort melhora as ordenações por