--- title: "Bubble Sort em Zig — Implementação e Explicação" url: "https://ziglang.com.br/algoritmos/bubble-sort-em-zig-implementa%C3%A7%C3%A3o-e-explica%C3%A7%C3%A3o/" markdown_url: "https://ziglang.com.br/algoritmos/bubble-sort-em-zig-implementa%C3%A7%C3%A3o-e-explica%C3%A7%C3%A3o.MD" description: "Aprenda o algoritmo Bubble Sort implementado em Zig. Explicação completa com código funcional, análise de complexidade e exemplos práticos." date: "2026-02-21" author: "Zig Brasil" --- # Bubble Sort em Zig — Implementação e Explicação Aprenda o algoritmo Bubble Sort implementado em Zig. Explicação completa com código funcional, análise de complexidade e exemplos práticos. # 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 ```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](/algoritmos/merge-sort/), [Quick Sort](/algoritmos/quick-sort/) ou [Heap Sort](/algoritmos/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](/algoritmos/selection-sort/) | O(n²) | O(n²) | O(n²) | O(1) | Não | | [Insertion Sort](/algoritmos/insertion-sort/) | O(n) | O(n²) | O(n²) | O(1) | Sim | ## Recursos Relacionados - [Selection Sort em Zig](/algoritmos/selection-sort/) — Outro algoritmo O(n²) simples - [Insertion Sort em Zig](/algoritmos/insertion-sort/) — Alternativa mais eficiente para listas pequenas - [Merge Sort em Zig](/algoritmos/merge-sort/) — Algoritmo O(n log n) estável - [Array Dinâmico em Zig](/estruturas-dados/array-dinamico/) — Estrutura de dados para armazenar elementos - [std.sort na stdlib](/stdlib/) — Função de ordenação da biblioteca padrão do Zig