---
title: "Radix Sort em Zig — Implementação e Explicação"
url: "https://ziglang.com.br/algoritmos/radix-sort-em-zig-implementa%C3%A7%C3%A3o-e-explica%C3%A7%C3%A3o/"
markdown_url: "https://ziglang.com.br/algoritmos/radix-sort-em-zig-implementa%C3%A7%C3%A3o-e-explica%C3%A7%C3%A3o.MD"
description: "Aprenda o algoritmo Radix Sort implementado em Zig. Ordenação linear por dígitos com Counting Sort como sub-rotina, código funcional e análise."
date: "2026-02-21"
author: "Zig Brasil"
---

# Radix Sort em Zig — Implementação e Explicação

Aprenda o algoritmo Radix Sort implementado em Zig. Ordenação linear por dígitos com Counting Sort como sub-rotina, código funcional e análise.


# Radix Sort em Zig — Implementação e Explicação

O **Radix Sort** (ordenação por raiz/dígitos) é um algoritmo de ordenação não-comparativo que ordena números processando cada dígito individualmente, do menos significativo (LSD) ao mais significativo (MSD), ou vice-versa. Utiliza um algoritmo estável (geralmente [Counting Sort](/algoritmos/counting-sort/)) como sub-rotina para cada dígito.

## Como Funciona (LSD — Least Significant Digit)

1. Encontre o número com mais dígitos
2. Para cada posição de dígito (unidade, dezena, centena...):
   - Ordene todos os números usando Counting Sort baseado apenas naquele dígito
   - A estabilidade do Counting Sort preserva a ordem dos dígitos anteriores

### Visualização do Processo

```
Array original: [170, 45, 75, 90, 802, 24, 2, 66]

Passo 1 — Ordenar pelo dígito das unidades:
  170(0) 90(0) 802(2) 2(2) 24(4) 45(5) 75(5) 66(6)
  → [170, 90, 802, 2, 24, 45, 75, 66]

Passo 2 — Ordenar pelo dígito das dezenas:
  802(0) 2(0) 24(2) 45(4) 66(6) 170(7) 75(7) 90(9)
  → [802, 2, 24, 45, 66, 170, 75, 90]

Passo 3 — Ordenar pelo dígito das centenas:
  2(0) 24(0) 45(0) 66(0) 75(0) 90(0) 170(1) 802(8)
  → [2, 24, 45, 66, 75, 90, 170, 802] ✓
```

## Implementação em Zig

```zig
const std = @import("std");
const Allocator = std.mem.Allocator;

/// Radix Sort LSD (Least Significant Digit) para inteiros não-negativos.
pub fn radixSort(allocator: Allocator, items: []u32) !void {
    if (items.len <= 1) return;

    // Encontra o valor máximo para saber quantos dígitos processar
    var max_val: u32 = 0;
    for (items) |v| {
        if (v > max_val) max_val = v;
    }

    // Array de saída temporário
    const saida = try allocator.alloc(u32, items.len);
    defer allocator.free(saida);

    // Ordena por cada dígito, começando pelo menos significativo
    var exp: u64 = 1;
    while (max_val / @as(u32, @intCast(exp)) > 0) : (exp *= 10) {
        countingSortPorDigito(items, saida, @intCast(exp));
    }
}

/// Counting Sort estável para um dígito específico.
fn countingSortPorDigito(items: []u32, saida: []u32, exp: u32) void {
    var contagem = [_]usize{0} ** 10; // dígitos 0-9

    // Conta ocorrências do dígito
    for (items) |v| {
        const digito = (v / exp) % 10;
        contagem[digito] += 1;
    }

    // Soma acumulada
    var i: usize = 1;
    while (i < 10) : (i += 1) {
        contagem[i] += contagem[i - 1];
    }

    // Posiciona (de trás para frente = estável)
    var j: usize = items.len;
    while (j > 0) {
        j -= 1;
        const digito = (items[j] / exp) % 10;
        contagem[digito] -= 1;
        saida[contagem[digito]] = items[j];
    }

    // Copia de volta
    @memcpy(items, saida);
}

/// Radix Sort em base 256 (por bytes) — mais eficiente para u32.
/// Processa 4 bytes em vez de ~10 dígitos decimais.
pub fn radixSort256(allocator: Allocator, items: []u32) !void {
    if (items.len <= 1) return;

    const saida = try allocator.alloc(u32, items.len);
    defer allocator.free(saida);

    // Processa cada byte (4 passagens para u32)
    comptime var byte_idx: u5 = 0;
    inline while (byte_idx < 4) : (byte_idx += 1) {
        const shift: u5 = byte_idx * 8;
        var contagem = [_]usize{0} ** 256;

        // Conta
        for (items) |v| {
            const byte_val = @as(u8, @truncate(v >> shift));
            contagem[byte_val] += 1;
        }

        // Acumula
        var i: usize = 1;
        while (i < 256) : (i += 1) {
            contagem[i] += contagem[i - 1];
        }

        // Posiciona
        var j: usize = items.len;
        while (j > 0) {
            j -= 1;
            const byte_val = @as(u8, @truncate(items[j] >> shift));
            contagem[byte_val] -= 1;
            saida[contagem[byte_val]] = items[j];
        }

        @memcpy(items, saida);
    }
}

pub fn main() !void {
    const stdout = std.io.getStdOut().writer();
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();
    const allocator = gpa.allocator();

    var numeros = [_]u32{ 170, 45, 75, 90, 802, 24, 2, 66 };

    try stdout.print("Original:  ", .{});
    for (numeros) |n| try stdout.print("{d} ", .{n});
    try stdout.print("\n", .{});

    try radixSort(allocator, &numeros);

    try stdout.print("Ordenado:  ", .{});
    for (numeros) |n| try stdout.print("{d} ", .{n});
    try stdout.print("\n", .{});

    // Versão base 256
    var nums2 = [_]u32{ 1000000, 500, 123456, 789, 42 };
    try radixSort256(allocator, &nums2);

    try stdout.print("Base 256:  ", .{});
    for (nums2) |n| try stdout.print("{d} ", .{n});
    try stdout.print("\n", .{});
}
```

## Análise de Complexidade

| Caso | Tempo | Espaço |
|------|-------|--------|
| **Todos os casos** | O(d × (n + k)) | O(n + k) |

Onde:
- `n` = número de elementos
- `d` = número de dígitos do maior número
- `k` = base (10 para decimal, 256 para bytes)

### Quando é Linear?

Se `d` e `k` são constantes (ex: inteiros de 32 bits em base 256 → d=4, k=256), a complexidade é efetivamente **O(n)**.

## Características

- **Estável**: Sim — herda a estabilidade do Counting Sort
- **In-place**: Não — requer O(n) de memória auxiliar
- **Não-comparativo**: processa dígitos individualmente
- **Versátil**: funciona com qualquer base (10, 16, 256...)

## LSD vs MSD

| Aspecto | LSD (Menos Significativo) | MSD (Mais Significativo) |
|---------|--------------------------|-------------------------|
| Direção | Dígito menor → maior | Dígito maior → menor |
| Estável | Sim | Requer cuidado |
| Uso | Inteiros de tamanho fixo | Strings de tamanho variável |

## Quando Usar

- **Inteiros de tamanho fixo**: muito eficiente para u32, u64
- **Grande volume de dados**: supera algoritmos comparativos O(n log n)
- **Intervalo grande de valores**: onde [Counting Sort](/algoritmos/counting-sort/) sozinho seria inviável

## Recursos Relacionados

- [Counting Sort em Zig](/algoritmos/counting-sort/) — Sub-rotina do Radix Sort
- [Quick Sort em Zig](/algoritmos/quick-sort/) — Alternativa comparativa
- [Merge Sort em Zig](/algoritmos/merge-sort/) — Outro algoritmo estável
- [String Hashing](/algoritmos/string-hashing/) — Radix Sort pode ordenar strings via hash
- [Array Dinâmico](/estruturas-dados/array-dinamico/) — Estrutura para armazenar dados