Radix sort
Origem: Wikipédia, a enciclopédia livre.
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.
Na ciência da computação, radix sort é uma algoritmo de ordenação que ordena inteiros processando dígitos individuais. Já que os inteiros podem representar strings composta de caracteres (ex, nome ou datas) e pontos flutuantes especialmente formatados, radix sort não é limitado somente a inteiros. Computadores na sua maioria internamente representam todos os tipo de dados por números binários, por isso processar os dígitos na forma de inteiros em grupos representados por dígitos binários se torna mais conveniente. Existem duas classificações do radix sorts que são elas:
- Least significant digit (LSD – Dígito menos significante) radix sorts; - Most significant digit (MSD – Dígito mais significante) radix sorts.
Radix sorts LSD começa do dígito menos significante até o mais significante. Radix sorts MSD trabalha no sentido contrário. As representações de inteiros que são processadas pelo algoritmo de ordenação são frequentemente chamadas de “chaves”, que podem existir por si próprias ou associadas a outros dados.
Radix sorts LSD tipicamente usa a seguinte ordem de ordenação: 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.
Radix sorts MSD usa a ordem lexicográfica, que é adequada para ordenação de strings, assim como palavras, ou representações inteiros fixa com tamanho fixo. A seqüência "b, c, d, e, f, g, h, i, j, ba" será ordenada lexicograficamente assim "b, ba, c, d, e, f, g, h, i, j". Se a ordenação lexicográfica é usada para ordenar representações de inteiros com tamanho variável, então a representação de números inteiros de 1 a 10 terá a saída 1, 10, 2, 3, 4, 5, 6, 7, 8, 9, já que as chaves mais curtas são selecionadas primeiro pela esquerda e pulando para direita com espaços em branco para fazer as chaves também serem chaves longas para cumprir o proposito determinado pela ordenação. LSD é um algoritmo de ordenação rápido e estável, que pode ser usado para ordenar chaves curtas em ordem lexicográfica. Chaves deve ser uma string de caracteres, ou numérica. O processo das chaves começa no dígito meno significante, o mais a direta, até o mais significante, o mais a esquerda. A seqüência que cada digito é processada pelo radix sort LSD é contraria a seqüência que cada digito é processada pelo radix sort MSD.
O radix sort LSD opera na notação Big O, em O(nk), onde n é o número de chaves, e o comprimento médio da chave. Você pode garantir esse desempenho para um comprimento variável da chave agrupando todas as chaves que tem o mesmo comprimento juntas e separadamente agindo como um radix sort LSD em cada grupo de chaves para cada comprimento, do mais curto para o mais comprido, em ordem para evitar o processamento de um lista inteira de chaves em cada passo da ordenação.
O algoritmo de ordenação radix foi originalmente usado para ordenar cartões perfurados em uma número grande de passos. Um algoritmo computador radix sort foi inventado em 1954 na MIT por Harold H. Seward. Em muitas aplicações em que seja necessário velocidade, o computador radix sort é uma melhora nas ordenações por comparação.
O radix sort LSD tem se mostrado uma alternativa de alta performance em relação a algoritmos baseados na comparação (assim como heapsort e o mergesort) que requerê comparações Ω(n · log n), onde n é o número de itens a serem ordenados. Algoritmos de ordenação baseados em comparações não atingem mais que Ω(n · log n) em tempo de execução, mas oferecem flexibilidade por ser aptos a ordenar respeitando formas mais complicadas de ordenação do que uma forma lexicográfica, no entanto, essa habilidade é de pouca importância em várias aplicações práticas.
Características
Complexidade de Tempo: Θ(nk).
Complexidade de espaço: Θ(n + s).
– n = número de elementos.
– k = tamanho string.
– s = tamanho do alfabeto.
Índice |
[editar] Implementações
[editar] Código em C#
private static void RadixSort(int[] a)
{
/* O radix
*/
int[] t = new int[a.Length]; // vetor auxiliar
int r = 4;// tamanho dos bits
int b = 32;//numero de bits de um inteiro
int[] count = new int[1 << r];
int[] pref = new int[1 << r];
int groups = (int)Math.Ceiling((double)b / (double)r);//numero de grupos
int mask = (1 << r) - 1;
for (int c = 0, shift = 0; c < groups; c++, shift += r)
{
for (int j = 0; j < count.Length; j++)
count[j] = 0;
for (int i = 0; i < a.Length; i++)
count[(a[i] >> shift) & mask]++;
pref[0] = 0;
for (int i = 1; i < count.Length; i++)
pref[i] = pref[i - 1] + count[i - 1];
for (int i = 0; i < a.Length; i++)
t[pref[(a[i] >> shift) & mask]++] = a[i];
t.CopyTo(a, 0);
}
}
[editar] Código em Java
private static final int MAX_CHARS = 28;
private static void radixSort (String [] v)
{
Queue queues [ ] = createQueues();
for ( int pos = maxSize( v ) - 1; pos >= 0; pos--)
{
for (int i = 0; i < v.length; i++)
{
int q = queueNo( v [ i ], pos );
queues [ q ].enqueue( v [ i ] );
}
restore ( queues, v );
}
}
private static void restore ( Queue [ ] qs, String [ ] v)
{
int contv = 0;
for ( int q = 0; q < qs.length; q++ )
while (! qs[ q ].empty( ) )
v [ contv++ ] = qs [ q ].dequeue( );
}
private static Queue[] createQueues()
{
Queue[] result = new Queue [ MAX_CHARS ];
for (int i = 0; i < MAX_CHARS; i++)
result [ i ] = new Queue();
return result ;
}
private static int queueNo ( String string , int pos)
{
if (pos >= string.length ())
return 0;
char ch = string .charAt(pos);
if (ch >= ’A’ && ch <= ’Z’)
return ch - ’A’ + 1;
else if (ch >= ’a’ && ch <= ’z’)
return ch - ’a’ + 1;
else
return 27;
}
private static int maxSize(String [] v)
{
int maiorValor = v[0]. length ();
for (int i = 1; i < v.length; i++)
if (maiorValor < v[i ]. length ())
maiorValor = v[i ]. length ();
return maiorValor;
}
[editar] Mesmo código, em python
MAX_CHARS = 28
def radix_sort(lista):
tamanho_maximo = max([len(palavra) for palavra in lista])
for pos in range(tamanho_maximo-1, -1, -1):
baldes = [list() for x in range(MAX_CHARS)]
for palavra in lista:
balde = numero_do_balde(palavra, pos)
baldes[balde] += [palavra]
lista = sum(baldes, [])
return lista
def numero_do_balde(palavra, pos):
if (pos >= len(palavra)): return 0
ch = palavra[pos]
if (ch >= 'A' and ch <= 'Z'): return ord(ch) - ord('A') + 1
if (ch >= 'a' and ch <= 'z'): return ord(ch) - ord('a') + 1
return MAX_CHARS-1
