Bubble Sort em Zig — Implementação e Explicação
O Bubble Sort (ordenação por bolha) é um dos algoritmos de ordenação mais simples e intuitivos. Ele funciona comparando pares adjacentes de elementos e trocando-os se estiverem na ordem errada. O processo se repete até que nenhuma troca seja necessária, indicando que a lista está ordenada.
Como Funciona
O algoritmo percorre repetidamente a lista, comparando elementos adjacentes. A cada passagem, o maior elemento não ordenado “sobe” para sua posição correta, como uma bolha subindo na água — daí o nome.
Visualização do Processo
Array inicial: [5, 3, 8, 1, 2]
Passagem 1:
[5, 3, 8, 1, 2] → compara 5,3 → troca → [3, 5, 8, 1, 2]
[3, 5, 8, 1, 2] → compara 5,8 → ok → [3, 5, 8, 1, 2]
[3, 5, 8, 1, 2] → compara 8,1 → troca → [3, 5, 1, 8, 2]
[3, 5, 1, 8, 2] → compara 8,2 → troca → [3, 5, 1, 2, 8] ✓ 8 na posição
Passagem 2:
[3, 5, 1, 2, 8] → compara 3,5 → ok → [3, 5, 1, 2, 8]
[3, 5, 1, 2, 8] → compara 5,1 → troca → [3, 1, 5, 2, 8]
[3, 1, 5, 2, 8] → compara 5,2 → troca → [3, 1, 2, 5, 8] ✓ 5 na posição
Passagem 3:
[3, 1, 2, 5, 8] → compara 3,1 → troca → [1, 3, 2, 5, 8]
[1, 3, 2, 5, 8] → compara 3,2 → troca → [1, 2, 3, 5, 8] ✓ 3 na posição
Resultado: [1, 2, 3, 5, 8] ✓
Implementação em Zig
const std = @import("std");
/// Bubble Sort genérico para slices de qualquer tipo comparável.
/// Ordena o slice in-place em ordem crescente.
pub fn bubbleSort(comptime T: type, items: []T) void {
const len = items.len;
if (len <= 1) return;
var i: usize = 0;
while (i < len - 1) : (i += 1) {
var trocou = false;
var j: usize = 0;
while (j < len - 1 - i) : (j += 1) {
if (items[j] > items[j + 1]) {
// Troca os elementos adjacentes
const temp = items[j];
items[j] = items[j + 1];
items[j + 1] = temp;
trocou = true;
}
}
// Otimização: se nenhuma troca ocorreu, o array já está ordenado
if (!trocou) break;
}
}
/// Versão com função de comparação personalizada
pub fn bubbleSortComparator(
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 trocou = false;
var j: usize = 0;
while (j < len - 1 - i) : (j += 1) {
if (lessThan(items[j + 1], items[j])) {
const temp = items[j];
items[j] = items[j + 1];
items[j + 1] = temp;
trocou = true;
}
}
if (!trocou) break;
}
}
pub fn main() !void {
const stdout = std.io.getStdOut().writer();
// Exemplo com inteiros
var numeros = [_]i32{ 64, 34, 25, 12, 22, 11, 90 };
try stdout.print("Array original: ", .{});
for (numeros) |n| try stdout.print("{d} ", .{n});
try stdout.print("\n", .{});
bubbleSort(i32, &numeros);
try stdout.print("Array ordenado: ", .{});
for (numeros) |n| try stdout.print("{d} ", .{n});
try stdout.print("\n", .{});
// Exemplo com ordem decrescente usando comparador
var desc = [_]i32{ 3, 7, 1, 9, 2 };
bubbleSortComparator(i32, &desc, struct {
fn f(a: i32, b: i32) bool {
return a > b; // ordem decrescente
}
}.f);
try stdout.print("Ordem decrescente: ", .{});
for (desc) |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, com otimização | O(1) |
| Caso médio | O(n²) | O(1) |
| Pior caso | O(n²) — array em ordem inversa | O(1) |
Por que O(n²)?
No pior caso, o algoritmo executa n-1 passagens, e em cada passagem faz até n-1 comparações. Isso resulta em aproximadamente (n-1) × (n-1) = n² - 2n + 1 comparações, que é O(n²).
Características
- Estável: Sim — elementos iguais mantêm sua ordem relativa original
- In-place: Sim — usa apenas O(1) de memória adicional
- Adaptativo: Sim (com a otimização) — detecta arrays já ordenados em O(n)
- Online: Não — precisa de todos os dados antes de começar
Quando Usar
O Bubble Sort é útil para:
- Fins educacionais: é o algoritmo mais fácil de entender e implementar
- Listas muito pequenas: para poucos elementos, a simplicidade compensa
- Dados quase ordenados: com a otimização de detecção de trocas, é eficiente
Para listas maiores, prefira algoritmos como Merge Sort, Quick Sort ou Heap Sort que têm complexidade O(n log n).
Comparação com Outros Algoritmos
| Algoritmo | Melhor | Médio | Pior | Espaço | Estável |
|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | Sim |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | Não |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | Sim |
Recursos Relacionados
- Selection Sort em Zig — Outro algoritmo O(n²) simples
- Insertion Sort em Zig — Alternativa mais eficiente para listas pequenas
- Merge Sort em Zig — Algoritmo O(n log n) estável
- Array Dinâmico em Zig — Estrutura de dados para armazenar elementos
- std.sort na stdlib — Função de ordenação da biblioteca padrão do Zig