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
- O primeiro elemento é considerado já ordenado
- Pegue o próximo elemento (chave)
- Compare a chave com os elementos à esquerda, da direita para a esquerda
- Desloque todos os elementos maiores que a chave uma posição à direita
- Insira a chave na posição correta
- 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
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 e Quick Sort para partições pequenas
Recursos Relacionados
- Bubble Sort em Zig — Outro algoritmo O(n²) simples
- Selection Sort em Zig — Ordenação por seleção
- Merge Sort em Zig — Algoritmo O(n log n) que usa Insertion Sort para partições pequenas
- Busca Binária em Zig — Base da variante Binary Insertion Sort
- Lista Encadeada — Insertion Sort é eficiente em listas encadeadas