Radix Sort
Última atualização
Radix sort é uma ordenação sem comparações para inteiros. Em vez de comparar valores, ele ordena os números dígito a dígito. A versão do dígito menos significativo (LSD) processa primeiro o dígito das unidades, depois as dezenas e então as centenas, usando um counting sort estável em cada dígito. Como cada passagem é estável, uma vez processado o dígito mais significativo o vetor inteiro fica ordenado. Pressione reproduzir acima para ver cada passagem de dígitos reordenar as barras.
Radix sort roda em tempo O(d·(n + k)), onde d é o número de dígitos e k é a base (10 aqui). Para inteiros de largura fixa isso é praticamente linear - pode superar as ordenações por comparação O(n log n) - mas só funciona com dados que possam ser divididos em dígitos ou chaves.
Complexidade de tempo e espaço
| Caso | Complexidade | Notas |
|---|---|---|
| Tempo | O(d·(n + k)) | d dígitos, base k (linear para d fixo) |
| Espaço | O(n + k) | Vetor de saída + contagens de dígitos |
| Estável | Sim | Cada passagem de dígito é um counting sort estável |
| Comparação? | Não | Ordena por dígito, não comparando valores |
| Funciona com | Inteiros/chaves | Não com objetos comparáveis gerais |
Passo a passo
| Passo | O que acontece |
|---|---|
| 1 | Encontrar o valor máximo para saber quantos dígitos processar. |
| 2 | Começar pelo dígito menos significativo (as unidades). |
| 3 | Ordenar o vetor de forma estável por esse dígito usando counting sort. |
| 4 | Passar para o próximo dígito mais significativo. |
| 5 | Repetir até processar todas as posições de dígitos. |
Exemplo resolvido
Ordenando [170, 45, 75, 90, 2, 24, 66]:
| Passagem | Vetor | Ação |
|---|---|---|
| Início | [170, 45, 75, 90, 2, 24, 66] | O máximo é 170, então são necessárias três passagens de dígitos. |
| Unidades | [170, 90, 2, 24, 45, 75, 66] | Ordenação estável pelo dígito das unidades: 0, 0, 2, 4, 5, 5, 6. |
| Dezenas | [2, 24, 45, 66, 170, 75, 90] | Ordenação estável pelo dígito das dezenas: 0, 2, 4, 6, 7, 7, 9 (170 mantém a dianteira sobre 75). |
| Centenas | [2, 24, 45, 66, 75, 90, 170] | Ordenação estável pelo dígito das centenas; só 170 tem um 1, então vai para o final. Ordenado. |
Quando usar o radix sort
| Use quando | Evite quando |
|---|---|
| As chaves são inteiros ou strings de comprimento fixo que você pode dividir em dígitos. | Você precisa ordenar objetos arbitrários com um comparador personalizado. |
As chaves têm um número pequeno e limitado de dígitos d, de modo que O(d·(n + k)) supera O(n log n). | As chaves são muito longas ou ilimitadas, tornando d grande e as passagens caras. |
Você precisa de uma ordenação estável e pode arcar com O(n + k) de espaço extra. | A memória é escassa e os buffers O(n + k) são inaceitáveis. |
O intervalo de valores ou a base k é modesto em relação a n. | k é enorme, então cada passagem de counting sort domina o tempo de execução. |
Código de Radix Sort
Uma implementação limpa e executável de Radix Sort em Python, JavaScript, Java, C++, C. Escolha uma linguagem, copie o código ou abra-o já carregado no Playground da Coddy.
Código de Radix Sort em Python
1def radix_sort(a):2 # Sort by each decimal digit, least significant first3 max_value = max(a)4 exp = 15 while max_value // exp > 0:6 a = sort_by_digit(a, exp)7 exp *= 108 return a9
10
11def sort_by_digit(a, exp):12 buckets = [[] for _ in range(10)]13 for value in a:14 digit = (value // exp) % 1015 buckets[digit].append(value)16 # Concatenating buckets 0..9 keeps the sort stable17 return [value for bucket in buckets for value in bucket]18
19
20nums = [170, 45, 75, 90, 802, 24, 2, 66]21print("Before:", nums)22print("After: ", radix_sort(nums))Código de Radix Sort em JavaScript
1function radixSort(arr) {2 let a = [...arr];3 const max = Math.max(...a);4 // One counting pass per digit, least significant first5 for (let exp = 1; Math.floor(max / exp) > 0; exp *= 10) {6 const buckets = Array.from({ length: 10 }, () => []);7 for (const x of a) {8 buckets[Math.floor(x / exp) % 10].push(x);9 }10 a = buckets.flat();11 }12 return a;13}14
15const data = [170, 45, 75, 90, 802, 24, 2, 66];16console.log("Before:", data);17console.log("Sorted:", radixSort(data));Código de Radix Sort em Java
1import java.util.Arrays;2
3public class Main {4 static void radixSort(int[] arr) {5 int max = 0;6 for (int v : arr) max = Math.max(max, v);7 // One stable counting pass per decimal digit8 for (int exp = 1; max / exp > 0; exp *= 10) countingPass(arr, exp);9 }10
11 static void countingPass(int[] arr, int exp) {12 int n = arr.length;13 int[] out = new int[n];14 int[] count = new int[10];15 for (int v : arr) count[(v / exp) % 10]++;16 for (int i = 1; i < 10; i++) count[i] += count[i - 1];17 // Walk backwards to keep the pass stable18 for (int i = n - 1; i >= 0; i--) {19 int digit = (arr[i] / exp) % 10;20 out[--count[digit]] = arr[i];21 }22 System.arraycopy(out, 0, arr, 0, n);23 }24
25 public static void main(String[] args) {26 int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};27 System.out.println("Before: " + Arrays.toString(arr));28 radixSort(arr);29 System.out.println("After: " + Arrays.toString(arr));30 }31}Código de Radix Sort em C++
1#include <algorithm>2#include <iostream>3#include <vector>4
5void printVec(const std::vector<int>& a) {6 for (int x : a) std::cout << x << " ";7 std::cout << "\n";8}9
10// Stable counting sort on one decimal digit (exp = 1, 10, 100, ...)11void countingPass(std::vector<int>& a, int exp) {12 std::vector<int> output(a.size());13 std::vector<int> count(10, 0);14 for (int x : a) ++count[(x / exp) % 10];15 for (int d = 1; d < 10; ++d) count[d] += count[d - 1];16 for (int i = static_cast<int>(a.size()) - 1; i >= 0; --i) {17 int digit = (a[i] / exp) % 10;18 output[--count[digit]] = a[i];19 }20 a = output;21}22
23void radixSort(std::vector<int>& a) {24 int maxVal = *std::max_element(a.begin(), a.end());25 for (int exp = 1; maxVal / exp > 0; exp *= 10) {26 countingPass(a, exp);27 }28}29
30int main() {31 std::vector<int> data = {170, 45, 75, 90, 802, 24, 2, 66};32 std::cout << "Before: ";33 printVec(data);34 radixSort(data);35 std::cout << "After: ";36 printVec(data);37 return 0;38}Código de Radix Sort em C
1#include <stdio.h>2#include <stdlib.h>3
4void printArr(const int a[], int n) {5 for (int i = 0; i < n; i++) printf("%d ", a[i]);6 printf("\n");7}8
9// Stable counting sort on one decimal digit (exp = 1, 10, 100, ...)10void countingPass(int a[], int n, int exp) {11 int* output = malloc(n * sizeof(int));12 int count[10] = {0};13 for (int i = 0; i < n; i++) count[(a[i] / exp) % 10]++;14 for (int d = 1; d < 10; d++) count[d] += count[d - 1];15 for (int i = n - 1; i >= 0; i--) {16 int digit = (a[i] / exp) % 10;17 output[--count[digit]] = a[i];18 }19 for (int i = 0; i < n; i++) a[i] = output[i];20 free(output);21}22
23void radixSort(int a[], int n) {24 int maxVal = a[0];25 for (int i = 1; i < n; i++) {26 if (a[i] > maxVal) maxVal = a[i];27 }28 for (int exp = 1; maxVal / exp > 0; exp *= 10) {29 countingPass(a, n, exp);30 }31}32
33int main(void) {34 int data[] = {170, 45, 75, 90, 802, 24, 2, 66};35 int n = sizeof(data) / sizeof(data[0]);36 printf("Before: ");37 printArr(data, n);38 radixSort(data, n);39 printf("After: ");40 printArr(data, n);41 return 0;42}Perguntas frequentes sobre Radix Sort
Qual é a complexidade de tempo do radix sort?
O(d·(n + k)), onde d é o número de dígitos e k é a base. Para inteiros de largura fixa isso é praticamente O(n), o que pode ser mais rápido que as ordenações por comparação. Ele usa O(n + k) de espaço extra.O radix sort é estável?
Sim. O radix sort LSD se baseia em um counting sort estável em cada dígito; a estabilidade é o que faz a abordagem dígito a dígito produzir um resultado corretamente ordenado.
Quando posso usar radix sort?
Radix sort funciona com dados que podem ser decompostos em dígitos ou chaves de tamanho fixo, como inteiros ou strings de comprimento fixo. Não é uma ordenação por comparação de propósito geral, então não consegue ordenar objetos arbitrários com um comparador personalizado.
Qual a diferença entre radix sort e counting sort?
k), o que lhe permite lidar com grandes intervalos de valores que o counting sort simples não conseguiria.Por que o radix sort LSD começa pelo dígito menos significativo?
Começar pelo dígito menos significativo permite que cada passagem estável preserve a ordenação estabelecida por todos os dígitos menos significativos anteriores. Quando o dígito mais significativo é processado, os empates nesse dígito já estão corretamente ordenados pelos dígitos inferiores, então o vetor fica totalmente ordenado. Ordenar primeiro pelo dígito mais significativo quebraria isso e exigiria uma abordagem recursiva diferente (radix sort MSD).
O radix sort consegue lidar com números negativos?
Não diretamente - a extração básica de dígitos assume inteiros não negativos. Soluções comuns são deslocar todos os valores somando o mínimo para que tudo fique não negativo, ou ordenar separadamente os negativos e os não negativos e depois concatenar. Ignorar isso é um erro frequente ao aplicar radix sort a dados reais.
Recursos relacionados
Mais visualizações
