std.sort em Zig — Referência e Exemplos

5 min de leitura
stdlib referência sort ordenação

std.sort — Ordenação de Dados

O módulo std.sort fornece algoritmos de ordenação eficientes para slices no Zig. A implementação padrão utiliza um algoritmo adaptativo (block sort / pdqsort) que oferece O(n log n) no caso médio, com otimizações para dados parcialmente ordenados. O módulo também expõe funções auxiliares como insertion para contextos específicos.

Visão Geral

const std = @import("std");
const sort = std.sort;

O std.sort trabalha com slices mutáveis e funções de comparação que seguem o padrão do Zig: recebem um contexto opcional e dois elementos, retornando .lt, .eq ou .gt.

Funções Principais

// Ordenação padrão (block sort — estável, O(n log n))
pub fn sort(comptime T: type, items: []T, context: anytype, comptime lessThan: fn (@TypeOf(context), T, T) bool) void

// Funções de comparação prontas
pub fn asc(comptime T: type) fn (void, T, T) bool
pub fn desc(comptime T: type) fn (void, T, T) bool

// Insertion sort — eficiente para arrays pequenos ou quase ordenados
pub fn insertion(comptime T: type, items: []T, context: anytype, comptime lessThan: fn (@TypeOf(context), T, T) bool) void

// Busca binária em slice ordenado
pub fn binarySearch(comptime T: type, items: []const T, target: T, context: anytype, comptime cmp: fn (@TypeOf(context), T, T) std.math.Order) ?usize

// Verifica se o slice está ordenado
pub fn isSorted(comptime T: type, items: []const T, context: anytype, comptime lessThan: fn (@TypeOf(context), T, T) bool) bool

Exemplo 1: Ordenação Básica

const std = @import("std");

pub fn main() !void {
    const stdout = std.io.getStdOut().writer();

    // Ordenação de inteiros
    var numeros = [_]i32{ 64, 25, 12, 22, 11, 90, 1, 45, 78, 33 };
    try stdout.print("Original:    {any}\n", .{numeros});

    // Ordem crescente
    std.mem.sort(i32, &numeros, {}, std.sort.asc(i32));
    try stdout.print("Crescente:   {any}\n", .{numeros});

    // Ordem decrescente
    std.mem.sort(i32, &numeros, {}, std.sort.desc(i32));
    try stdout.print("Decrescente: {any}\n", .{numeros});

    // Ordenação de floats
    var temperaturas = [_]f64{ 36.5, 38.1, 37.0, 39.2, 36.8, 37.5 };
    std.mem.sort(f64, &temperaturas, {}, std.sort.asc(f64));
    try stdout.writeAll("\nTemperaturas ordenadas: ");
    for (temperaturas, 0..) |t, i| {
        if (i > 0) try stdout.writeAll(", ");
        try stdout.print("{d:.1}", .{t});
    }
    try stdout.writeAll("\n");

    // Verificar se está ordenado
    const ordenado = std.sort.isSorted(f64, &temperaturas, {}, std.sort.asc(f64));
    try stdout.print("Está ordenado: {}\n", .{ordenado});
}

Exemplo 2: Comparadores Customizados

const std = @import("std");

const Aluno = struct {
    nome: []const u8,
    nota: f32,
    idade: u8,
};

fn compararPorNota(_: void, a: Aluno, b: Aluno) bool {
    return a.nota > b.nota; // Decrescente por nota
}

fn compararPorIdade(_: void, a: Aluno, b: Aluno) bool {
    return a.idade < b.idade; // Crescente por idade
}

fn compararPorNome(_: void, a: Aluno, b: Aluno) bool {
    return std.mem.order(u8, a.nome, b.nome) == .lt;
}

pub fn main() !void {
    const stdout = std.io.getStdOut().writer();

    var alunos = [_]Aluno{
        .{ .nome = "Carlos", .nota = 8.5, .idade = 22 },
        .{ .nome = "Ana", .nota = 9.2, .idade = 20 },
        .{ .nome = "Bruno", .nota = 7.8, .idade = 23 },
        .{ .nome = "Diana", .nota = 9.5, .idade = 21 },
        .{ .nome = "Eduardo", .nota = 8.0, .idade = 22 },
    };

    // Ordenar por nota (maior primeiro)
    std.mem.sort(Aluno, &alunos, {}, compararPorNota);
    try stdout.writeAll("=== Por Nota (decrescente) ===\n");
    for (alunos) |a| {
        try stdout.print("  {s:<10} nota={d:.1}  idade={d}\n", .{ a.nome, a.nota, a.idade });
    }

    // Ordenar por nome
    std.mem.sort(Aluno, &alunos, {}, compararPorNome);
    try stdout.writeAll("\n=== Por Nome (alfabética) ===\n");
    for (alunos) |a| {
        try stdout.print("  {s:<10} nota={d:.1}  idade={d}\n", .{ a.nome, a.nota, a.idade });
    }

    // Ordenar por idade
    std.mem.sort(Aluno, &alunos, {}, compararPorIdade);
    try stdout.writeAll("\n=== Por Idade (crescente) ===\n");
    for (alunos) |a| {
        try stdout.print("  {s:<10} nota={d:.1}  idade={d}\n", .{ a.nome, a.nota, a.idade });
    }
}

Exemplo 3: Insertion Sort para Arrays Pequenos

const std = @import("std");

pub fn main() !void {
    const stdout = std.io.getStdOut().writer();

    // Insertion sort é mais eficiente para arrays pequenos (< ~20 elementos)
    // ou arrays quase ordenados
    var pequeno = [_]i32{ 5, 2, 8, 1, 9, 3 };
    try stdout.print("Antes:  {any}\n", .{pequeno});

    std.sort.insertion(i32, &pequeno, {}, std.sort.asc(i32));
    try stdout.print("Depois: {any}\n", .{pequeno});

    // Comparação de performance: insertion vs. sort padrão
    var timer = try std.time.Timer.start();

    // Array quase ordenado — insertion sort brilha aqui
    var quase_ordenado: [100]i32 = undefined;
    for (&quase_ordenado, 0..) |*v, i| {
        v.* = @intCast(i);
    }
    // Perturba levemente
    quase_ordenado[10] = 95;
    quase_ordenado[50] = 3;
    quase_ordenado[80] = 15;

    timer.reset();
    std.sort.insertion(i32, &quase_ordenado, {}, std.sort.asc(i32));
    const tempo_insertion = timer.read();

    try stdout.print("\nInsertion sort (quase ordenado): {d} ns\n", .{tempo_insertion});
    try stdout.print("Ordenado: {}\n", .{std.sort.isSorted(i32, &quase_ordenado, {}, std.sort.asc(i32))});
}

Exemplo 4: Busca Binária em Dados Ordenados

const std = @import("std");

const Produto = struct {
    codigo: u32,
    nome: []const u8,
    preco: f64,
};

fn compararCodigo(_: void, produto: Produto, alvo: Produto) std.math.Order {
    return std.math.order(produto.codigo, alvo.codigo);
}

pub fn main() !void {
    const stdout = std.io.getStdOut().writer();

    // Dados já ordenados por código
    const produtos = [_]Produto{
        .{ .codigo = 101, .nome = "Teclado", .preco = 150.00 },
        .{ .codigo = 205, .nome = "Mouse", .preco = 80.00 },
        .{ .codigo = 310, .nome = "Monitor", .preco = 1200.00 },
        .{ .codigo = 412, .nome = "Headset", .preco = 250.00 },
        .{ .codigo = 520, .nome = "Webcam", .preco = 350.00 },
        .{ .codigo = 633, .nome = "Hub USB", .preco = 120.00 },
        .{ .codigo = 745, .nome = "SSD", .preco = 400.00 },
        .{ .codigo = 891, .nome = "RAM 16GB", .preco = 300.00 },
    };

    // Busca por código usando busca binária
    const codigos_busca = [_]u32{ 310, 520, 999, 101 };

    try stdout.writeAll("=== Busca de Produtos ===\n\n");
    for (codigos_busca) |codigo| {
        const alvo = Produto{ .codigo = codigo, .nome = "", .preco = 0 };
        if (std.sort.binarySearch(Produto, &produtos, alvo, {}, compararCodigo)) |idx| {
            const p = produtos[idx];
            try stdout.print("Código {d}: {s} — R$ {d:.2}\n", .{ codigo, p.nome, p.preco });
        } else {
            try stdout.print("Código {d}: não encontrado\n", .{codigo});
        }
    }

    // Lower bound — encontrar posição de inserção
    try stdout.writeAll("\n=== Produtos até R$ 300 ===\n");
    for (produtos) |p| {
        if (p.preco <= 300.0) {
            try stdout.print("  {s} (R$ {d:.2})\n", .{ p.nome, p.preco });
        }
    }
}

Análise de Complexidade

AlgoritmoMelhorMédioPiorEstávelMemória
sort (block sort)O(n)O(n log n)O(n log n)SimO(1)
insertionO(n)O(n^2)O(n^2)SimO(1)
binarySearchO(1)O(log n)O(log n)—O(1)

Quando Usar Cada Algoritmo

  • std.mem.sort / std.sort.sort — escolha padrão para quase todos os casos
  • std.sort.insertion — arrays com menos de ~20 elementos ou quase ordenados
  • std.sort.binarySearch — busca eficiente em dados já ordenados

Módulos Relacionados

Tutoriais Relacionados

Explore Mais

🚀 Primeiros Passos 🔧 Build System 📋 Receitas Prontas 💼 Vagas e Carreira ❓ FAQ (50 Perguntas) 🔄 Migrar de Outra Linguagem

Artigos relacionados

Continue aprendendo Zig

Explore mais tutoriais e artigos em português para dominar a linguagem Zig.

📚 Ver Todos os Tutoriais 💬 Junte-se à Comunidade