Radix Sort
Ordena dígito por dígito, do menos significativo ao mais significativo — sem nenhuma comparação entre elementos.
O(n)O(n)Como Funciona
Passo a passo do algoritmo
Identifique o número de dígitos
Encontre o valor máximo no array para determinar quantas passagens serão necessárias. Para números de d dígitos, o algoritmo fará d passagens.
maxVal = max(array)
d = floor(log10(maxVal)) + 1Ordene pelo dígito menos significativo
Na primeira passagem, distribua os elementos em 10 baldes (0-9) com base no dígito das unidades. Colete os baldes em ordem para obter um array parcialmente organizado.
balde = array[i] % 10
baldes[balde].add(array[i])Repita para cada posição
Repita o processo para dezenas, centenas, etc. Em cada passagem, os elementos são redistribuídos nos baldes com base no dígito atual.
divisor = 10^posição
balde = (array[i] / divisor) % 10Colete os baldes em ordem
Após cada passagem, colete os elementos dos baldes 0 a 9 em sequência. A ordem dos baldes garante a estabilidade do algoritmo.
para balde de 0 a 9: array.add(balde[i])Array ordenado após d passagens
Após processar todos os dígitos, o array estará completamente ordenado. O algoritmo é linear em relação ao número de elementos vezes o número de dígitos.
// O(d * n) onde d = número de dígitosImplementação
Código comentado em JavaScript e Python
function radixSort(array) {
const max = Math.max(...array);
// Faz uma passagem para cada posição de dígito
for (let exp = 1; Math.floor(max / exp) > 0; exp *= 10) {
contarOrdenar(array, exp);
}
return array;
}
function contarOrdenar(array, exp) {
const n = array.length;
const saida = new Array(n);
const contagem = new Array(10).fill(0);
// Conta ocorrências de cada dígito
for (let i = 0; i < n; i++) {
const digito = Math.floor(array[i] / exp) % 10;
contagem[digito]++;
}
// Acumula contagens para posições finais
for (let i = 1; i < 10; i++) {
contagem[i] += contagem[i - 1];
}
// Constrói o array de saída (de trás para frente para estabilidade)
for (let i = n - 1; i >= 0; i--) {
const digito = Math.floor(array[i] / exp) % 10;
saida[contagem[digito] - 1] = array[i];
contagem[digito]--;
}
// Copia de volta para o array original
for (let i = 0; i < n; i++) {
array[i] = saida[i];
}
}
// Exemplo de uso
const arr = [170, 45, 75, 90, 802, 24, 2, 66];
console.log(radixSort(arr)); // [2, 24, 45, 66, 75, 90, 170, 802]Playground
Veja o Radix Sort ordenando dígito por dígito, sem comparações
Quando Usar
Cenários ideais para este algoritmo
Números inteiros grandes
Ideal para ordenar grandes conjuntos de inteiros — supera algoritmos de comparação quando n é muito grande.
Strings de tamanho fixo
Eficiente para strings de comprimento fixo (como CEPs, CPFs) — trate cada caractere como um "dígito".
Dados com intervalo conhecido
Quando o número de dígitos é pequeno e conhecido antecipadamente, o Radix Sort oferece desempenho linear garantido.
Ordenação estável
O Radix Sort é estável por construção — elementos com o mesmo dígito mantêm sua ordem relativa original.
Complexidade
Análise de desempenho por cenário
| Cenário | Tempo |
|---|---|
| Melhor caso | O(n) |
| Caso médio | O(n) |
| Pior caso | O(n) |