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.
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 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
