---
title: "Selection Sort em Zig — Implementação e Explicação"
url: "https://ziglang.com.br/algoritmos/selection-sort-em-zig-implementa%C3%A7%C3%A3o-e-explica%C3%A7%C3%A3o/"
markdown_url: "https://ziglang.com.br/algoritmos/selection-sort-em-zig-implementa%C3%A7%C3%A3o-e-explica%C3%A7%C3%A3o.MD"
description: "Aprenda o algoritmo Selection Sort implementado em Zig. Explicação detalhada com código funcional, análise de complexidade e exemplos práticos."
date: "2026-02-21"
author: "Zig Brasil"
---

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

Aprenda o algoritmo Selection Sort implementado em Zig. Explicação detalhada com código funcional, análise de complexidade e exemplos práticos.


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

O **Selection Sort** (ordenação por seleção) é um algoritmo de ordenação simples que funciona dividindo o array em duas partes: a porção já ordenada (à esquerda) e a porção não ordenada (à direita). A cada iteração, o algoritmo seleciona o menor elemento da porção não ordenada e o coloca na posição correta.

## Como Funciona

1. Encontre o menor elemento no array inteiro
2. Troque-o com o primeiro elemento
3. Encontre o menor elemento no subarray restante (excluindo o primeiro)
4. Troque-o com o segundo elemento
5. Repita até que todo o array esteja ordenado

### Visualização do Processo

```
Array inicial: [29, 10, 14, 37, 13]
                ↑ parte ordenada | parte não ordenada

Passo 1: menor = 10 (posição 1) → troca com posição 0
  [10 | 29, 14, 37, 13]
   ✓

Passo 2: menor = 13 (posição 4) → troca com posição 1
  [10, 13 | 14, 37, 29]
   ✓   ✓

Passo 3: menor = 14 (posição 2) → já na posição certa
  [10, 13, 14 | 37, 29]
   ✓   ✓   ✓

Passo 4: menor = 29 (posição 4) → troca com posição 3
  [10, 13, 14, 29 | 37]
   ✓   ✓   ✓   ✓

Resultado: [10, 13, 14, 29, 37] ✓
```

## Implementação em Zig

```zig
const std = @import("std");

/// Selection Sort genérico para slices de qualquer tipo comparável.
/// Ordena o slice in-place em ordem crescente.
pub fn selectionSort(comptime T: type, items: []T) void {
    const len = items.len;
    if (len <= 1) return;

    var i: usize = 0;
    while (i < len - 1) : (i += 1) {
        // Encontra o índice do menor elemento na parte não ordenada
        var min_idx: usize = i;
        var j: usize = i + 1;
        while (j < len) : (j += 1) {
            if (items[j] < items[min_idx]) {
                min_idx = j;
            }
        }

        // Troca o menor encontrado com o elemento na posição i
        if (min_idx != i) {
            const temp = items[i];
            items[i] = items[min_idx];
            items[min_idx] = temp;
        }
    }
}

/// Versão com função de comparação personalizada
pub fn selectionSortBy(
    comptime T: type,
    items: []T,
    comptime lessThan: fn (T, T) bool,
) void {
    const len = items.len;
    if (len <= 1) return;

    var i: usize = 0;
    while (i < len - 1) : (i += 1) {
        var min_idx: usize = i;
        var j: usize = i + 1;
        while (j < len) : (j += 1) {
            if (lessThan(items[j], items[min_idx])) {
                min_idx = j;
            }
        }
        if (min_idx != i) {
            const temp = items[i];
            items[i] = items[min_idx];
            items[min_idx] = temp;
        }
    }
}

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

    var numeros = [_]i32{ 64, 25, 12, 22, 11 };

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

    selectionSort(i32, &numeros);

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

    // Exemplo com floats em ordem decrescente
    var floats = [_]f64{ 3.14, 1.41, 2.72, 0.58, 1.73 };
    selectionSortBy(f64, &floats, struct {
        fn f(a: f64, b: f64) bool {
            return a > b;
        }
    }.f);

    try stdout.print("Floats decrescente: ", .{});
    for (floats) |n| try stdout.print("{d:.2} ", .{n});
    try stdout.print("\n", .{});
}
```

## Análise de Complexidade

| Caso | Tempo | Espaço |
|------|-------|--------|
| **Melhor caso** | O(n²) | O(1) |
| **Caso médio** | O(n²) | O(1) |
| **Pior caso** | O(n²) | O(1) |

### Por que sempre O(n²)?

Diferente do [Bubble Sort](/algoritmos/bubble-sort/), o Selection Sort não tem otimização para arrays já ordenados. Ele sempre precisa percorrer toda a parte não ordenada para encontrar o mínimo, resultando em `n + (n-1) + (n-2) + ... + 1 = n(n-1)/2` comparações.

A vantagem é que faz **no máximo n-1 trocas**, muito menos que o Bubble Sort que pode fazer O(n²) trocas. Isso é útil quando o custo de trocar elementos é alto.

## Características

- **Estável**: Não — a troca pode alterar a ordem de elementos iguais
- **In-place**: Sim — usa apenas O(1) de memória adicional
- **Adaptativo**: Não — sempre faz O(n²) comparações
- **Número de trocas**: O(n) — vantagem quando trocas são custosas

## Quando Usar

O Selection Sort é adequado para:
- **Arrays pequenos**: a simplicidade compensa para poucos elementos
- **Trocas custosas**: faz o mínimo de trocas (no máximo n-1)
- **Fins educacionais**: fácil de entender e implementar

Para listas maiores, prefira algoritmos com complexidade O(n log n) como [Merge Sort](/algoritmos/merge-sort/) ou [Quick Sort](/algoritmos/quick-sort/).

## Variante: Seleção Dupla

Uma otimização possível é encontrar tanto o menor quanto o maior elemento em cada passagem, reduzindo o número de passagens pela metade:

```zig
pub fn doubleSelectionSort(comptime T: type, items: []T) void {
    const len = items.len;
    if (len <= 1) return;

    var esquerda: usize = 0;
    var direita: usize = len - 1;

    while (esquerda < direita) {
        var min_idx: usize = esquerda;
        var max_idx: usize = esquerda;

        var i: usize = esquerda;
        while (i <= direita) : (i += 1) {
            if (items[i] < items[min_idx]) min_idx = i;
            if (items[i] > items[max_idx]) max_idx = i;
        }

        // Troca o mínimo para a esquerda
        const temp_min = items[esquerda];
        items[esquerda] = items[min_idx];
        items[min_idx] = temp_min;

        // Ajusta max_idx se foi afetado pela troca anterior
        if (max_idx == esquerda) max_idx = min_idx;

        // Troca o máximo para a direita
        const temp_max = items[direita];
        items[direita] = items[max_idx];
        items[max_idx] = temp_max;

        esquerda += 1;
        direita -= 1;
    }
}
```

## Recursos Relacionados

- [Bubble Sort em Zig](/algoritmos/bubble-sort/) — Algoritmo simples por troca de adjacentes
- [Insertion Sort em Zig](/algoritmos/insertion-sort/) — Melhor alternativa para listas pequenas
- [Heap Sort em Zig](/algoritmos/heap-sort/) — Versão otimizada da ideia de seleção
- [Array Estático em Zig](/estruturas-dados/array-estatico/) — Estrutura base para ordenação
- [Heap Binário](/estruturas-dados/heap-binario/) — Estrutura que otimiza a seleção do mínimo