Loading AI tools
Da 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 em qualquer ordem relacionada com a lexicografia.
Este artigo não cita fontes confiáveis. (Julho de 2015) |
Radix sort | |
---|---|
classe | Algoritmo de ordenação |
estrutura de dados | Array, Listas ligadas |
complexidade pior caso | |
complexidade de espaços pior caso | |
otimo | exatamente correto |
estabilidade | estável |
Algoritmos | |
Na ciência da computação, radix sort é um algoritmo de ordenação que ordena inteiros processando dígitos individuais. Como os inteiros podem representar strings compostas de caracteres (como nomes ou datas) e pontos flutuantes especialmente formatados, radix sort não é limitado somente a inteiros.
Computadores, na sua maioria, representam internamente todos os tipo de dados como 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 sort, que são:
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 sequê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.
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".
O radix sort LSD opera na notação Big-O, em , onde é o número de chaves, e é 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 uma lista inteira de chaves em cada passo da ordenação.
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 comparações, onde é 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.
O algoritmo de ordenação radix sort 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.
A complexidade no tempo do algoritmo é e a complexidade no espaço: , onde
function vetor = radixsort(vetor, tamanho)
%
% Ordena vetor de inteiros, exemplo:
% tamanho = 10000;
% vetor = floor(10000*rand(tamanho,1));
% vetor = radixsort(vetor, tamanho);
%
ep = 1;
maior = max(vetor);
while floor(maior/ep) > 0
V = sortrows([mod(floor(vetor/ep), 10), (1:tamanho)']);
vetor = vetor(V(:,2));
ep = ep*10;
end
end
void radixsort(int vetor[], int tamanho) {
int i;
int *b;
int maior = vetor[0];
int exp = 1;
b = (int *)calloc(tamanho, sizeof(int));
for (i = 0; i < tamanho; i++) {
if (vetor[i] > maior)
maior = vetor[i];
}
while (maior/exp > 0) {
int bucket[10] = { 0 };
for (i = 0; i < tamanho; i++)
bucket[(vetor[i] / exp) % 10]++;
for (i = 1; i < 10; i++)
bucket[i] += bucket[i - 1];
for (i = tamanho - 1; i >= 0; i--)
b[--bucket[(vetor[i] / exp) % 10]] = vetor[i];
for (i = 0; i < tamanho; i++)
vetor[i] = b[i];
exp *= 10;
}
free(b);
}
static void RadixSort(int[] vetor) {
int i;
int[] b;
int maior = vetor[0];
int exp = 1;
b = new int[vetor.Length];
for (i = 0; i < vetor.Length; i++) {
if (vetor[i] > maior)
maior = vetor[i];
}
while (maior/exp > 0) {
int[] bucket = new int[10];
for (i = 0; i < vetor.Length; i++)
bucket[(vetor[i] / exp) % 10]++;
for (i = 1; i < 10; i++)
bucket[i] += bucket[i - 1];
for (i = vetor.Length - 1; i >= 0; i--)
b[--bucket[(vetor[i] / exp) % 10]] = vetor[i];
for (i = 0; i < vetor.Length; i++)
vetor[i] = b[i];
exp *= 10;
}
}
import java.util.*;
public class TestRadix {
private static final int MAX_CHARS = 28;
private static void radixSort(String[] v) {
Queue<String> 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].add(v[i]);
}
restore(queues, v);
}
}
private static void restore(Queue<String>[] qs, String[] v) {
int contv = 0;
for (int q = 0; q < qs.length; q++)
while (qs[q].size() > 0)
v[contv++] = qs[q].remove();
}
private static Queue<String>[] createQueues() {
LinkedList<String>[] result = new LinkedList[MAX_CHARS];
for (int i = 0; i < MAX_CHARS; i++) {
result[i] = new LinkedList<String>();
}
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 maxValue = v[0].length();
for (int i = 1; i < v.length; i++) {
if (maxValue < v[i].length()) {
maxValue = v[i].length();
}
}
return maxValue;
}
public static void printStringArray(String[] arrToPrint) {
for (int i = 0; i < arrToPrint.length; i++) {
System.out.print(arrToPrint[i]+" ");
}
System.out.println();
}
/**
* @param args Array of strings (set of words) to be sorted (ordered) - Must be passed as parameters
*/
public static void main(String[] args) {
System.out.print("Input: ");
printStringArray(args);
radixSort(args);
System.out.print("\nOutput: ");
printStringArray(args);
}
}
public void radixSort(int vector[]){
for(int digit = 0; digit < 3; digit ++){
int power = (int) Math.pow(10, digit+1);
int z[][] = new int[vector.length][10];
int n[] = new int[10];
for(int i = 0; i < vector.length; i ++){
int num = vector[i];
z[n[(num%power)/(power/10)]][(num%power)/(power/10)] = num;
n[(num%power)/(power/10)]++;
}
int c = 0;
for(int i = 0; i < 10; i ++){
for(int j = 0; j < vector.length; j ++){
if(j < n[i]){
vector[c] = z[j][i];
c++;
}else{break;}
}
}
}
}
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 y 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
function radix_sort (&$a, $n)
{
$r = 8;
$R = 256;
$p = 4;
$count = null;
for ($i = 0; $i < $p; ++$i)
{
for ($j = 0; $j < $R; ++$j)
$count[$j] = 0;
for ($k = 0; $k < $n; ++$k)
{
$pos = ($a[$k] >> (r * $i)) & ($R - 1);
$count[pos] += 1;
$tempArray[$k] = $a[$k];
}
$pos = 0;
for ($j = 0; $j < $R; ++$j)
{
$tmp = $pos;
$pos += $count[$j];
$count[$j] = $tmp;
}
for ($k = 0; $k < $n; ++$k)
{
$pos = (tempArray[$k] >> ($r * $j)) & ($R - 2);
$a[$count[$pos]] = $tempArray[$k];
$count[$pos] += 1;
}
}
}
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.