---
title: "Insertion Sort em Zig — Implementação e Explicação"
url: "https://ziglang.com.br/algoritmos/insertion-sort-em-zig-implementa%C3%A7%C3%A3o-e-explica%C3%A7%C3%A3o/"
markdown_url: "https://ziglang.com.br/algoritmos/insertion-sort-em-zig-implementa%C3%A7%C3%A3o-e-explica%C3%A7%C3%A3o.MD"
description: "Aprenda o algoritmo Insertion 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"
---

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

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


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

O **Insertion Sort** (ordenação por inserção) é um algoritmo simples que constrói a lista ordenada um elemento por vez. Funciona de maneira semelhante à forma como organizamos cartas na mão: pegamos uma carta e a inserimos na posição correta entre as cartas já ordenadas.

## Como Funciona

1. O primeiro elemento é considerado já ordenado
2. Pegue o próximo elemento (chave)
3. Compare a chave com os elementos à esquerda, da direita para a esquerda
4. Desloque todos os elementos maiores que a chave uma posição à direita
5. Insira a chave na posição correta
6. Repita para todos os elementos

### Visualização do Processo

```
Array inicial: [5, 2, 4, 6, 1, 3]

Passo 1: chave = 2, compara com 5
  [5, 5, 4, 6, 1, 3]  → desloca 5
  [2, 5, 4, 6, 1, 3]  → insere 2
   ↑ ordenado

Passo 2: chave = 4, compara com 5
  [2, 5, 5, 6, 1, 3]  → desloca 5
  [2, 4, 5, 6, 1, 3]  → insere 4
   ↑──↑ ordenado

Passo 3: chave = 6, compara com 5 → já na posição
  [2, 4, 5, 6, 1, 3]
   ↑─────↑ ordenado

Passo 4: chave = 1, desloca 6, 5, 4, 2
  [1, 2, 4, 5, 6, 3]  → insere 1
   ↑────────↑ ordenado

Passo 5: chave = 3, desloca 6, 5, 4
  [1, 2, 3, 4, 5, 6]  → insere 3
   ↑───────────↑ ordenado ✓
```

## Implementação em Zig

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

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

    var i: usize = 1;
    while (i < len) : (i += 1) {
        const chave = items[i];

        // Move elementos maiores que a chave uma posição à frente
        var j: usize = i;
        while (j > 0 and items[j - 1] > chave) {
            items[j] = items[j - 1];
            j -= 1;
        }
        items[j] = chave;
    }
}

/// Versão com comparador personalizado
pub fn insertionSortBy(
    comptime T: type,
    items: []T,
    comptime lessThan: fn (T, T) bool,
) void {
    const len = items.len;
    if (len <= 1) return;

    var i: usize = 1;
    while (i < len) : (i += 1) {
        const chave = items[i];
        var j: usize = i;
        while (j > 0 and lessThan(chave, items[j - 1])) {
            items[j] = items[j - 1];
            j -= 1;
        }
        items[j] = chave;
    }
}

/// Binary Insertion Sort: usa busca binária para encontrar
/// a posição de inserção, reduzindo comparações para O(n log n).
/// O número de deslocamentos permanece O(n²).
pub fn binaryInsertionSort(comptime T: type, items: []T) void {
    const len = items.len;
    if (len <= 1) return;

    var i: usize = 1;
    while (i < len) : (i += 1) {
        const chave = items[i];

        // Busca binária para encontrar a posição de inserção
        var esquerda: usize = 0;
        var direita: usize = i;
        while (esquerda < direita) {
            const meio = esquerda + (direita - esquerda) / 2;
            if (items[meio] > chave) {
                direita = meio;
            } else {
                esquerda = meio + 1;
            }
        }

        // Desloca elementos para abrir espaço
        var j: usize = i;
        while (j > esquerda) : (j -= 1) {
            items[j] = items[j - 1];
        }
        items[esquerda] = chave;
    }
}

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

    var numeros = [_]i32{ 12, 11, 13, 5, 6 };

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

    insertionSort(i32, &numeros);

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

    // Binary Insertion Sort
    var nums2 = [_]i32{ 37, 23, 0, 17, 12, 72, 31 };
    binaryInsertionSort(i32, &nums2);

    try stdout.print("Binário:   ", .{});
    for (nums2) |n| try stdout.print("{d} ", .{n});
    try stdout.print("\n", .{});
}
```

## Análise de Complexidade

| Caso | Tempo | Espaço |
|------|-------|--------|
| **Melhor caso** | O(n) — array já ordenado | O(1) |
| **Caso médio** | O(n²) | O(1) |
| **Pior caso** | O(n²) — array em ordem inversa | O(1) |

### Desempenho na Prática

Apesar de ser O(n²), o Insertion Sort tem vantagens práticas:
- É o **mais rápido** entre os O(n²) para listas pequenas (n < 20)
- Tem baixo overhead constante
- É **excelente para dados quase ordenados** — apenas O(n) nesse caso
- Por isso, é usado como base em algoritmos híbridos como Timsort e Introsort

## Características

- **Estável**: Sim — preserva a ordem de elementos iguais
- **In-place**: Sim — O(1) de memória extra
- **Adaptativo**: Sim — O(n) para dados quase ordenados
- **Online**: Sim — pode ordenar à medida que recebe dados

## Quando Usar

- **Listas pequenas** (n < 20-50): mais rápido que algoritmos sofisticados
- **Dados quase ordenados**: desempenho próximo de O(n)
- **Recebimento contínuo de dados**: é um algoritmo online
- **Como sub-rotina**: usado dentro do [Merge Sort](/algoritmos/merge-sort/) e [Quick Sort](/algoritmos/quick-sort/) para partições pequenas

## Recursos Relacionados

- [Bubble Sort em Zig](/algoritmos/bubble-sort/) — Outro algoritmo O(n²) simples
- [Selection Sort em Zig](/algoritmos/selection-sort/) — Ordenação por seleção
- [Merge Sort em Zig](/algoritmos/merge-sort/) — Algoritmo O(n log n) que usa Insertion Sort para partições pequenas
- [Busca Binária em Zig](/algoritmos/busca-binaria/) — Base da variante Binary Insertion Sort
- [Lista Encadeada](/estruturas-dados/lista-encadeada/) — Insertion Sort é eficiente em listas encadeadas