--- title: "Quick Sort em Zig — Implementação e Explicação" url: "https://ziglang.com.br/algoritmos/quick-sort-em-zig-implementa%C3%A7%C3%A3o-e-explica%C3%A7%C3%A3o/" markdown_url: "https://ziglang.com.br/algoritmos/quick-sort-em-zig-implementa%C3%A7%C3%A3o-e-explica%C3%A7%C3%A3o.MD" description: "Aprenda o algoritmo Quick Sort implementado em Zig. Explicação detalhada com código funcional, particionamento Lomuto e Hoare, e análise completa." date: "2026-02-21" author: "Zig Brasil" --- # Quick Sort em Zig — Implementação e Explicação Aprenda o algoritmo Quick Sort implementado em Zig. Explicação detalhada com código funcional, particionamento Lomuto e Hoare, e análise completa. # Quick Sort em Zig — Implementação e Explicação O **Quick Sort** (ordenação rápida) é um dos algoritmos de ordenação mais utilizados na prática. Baseado na técnica de **divisão e conquista**, ele seleciona um elemento como pivô e particiona o array de forma que todos os elementos menores fiquem à esquerda e os maiores à direita. ## Como Funciona 1. **Escolher pivô**: selecione um elemento do array (último, primeiro, mediana, ou aleatório) 2. **Particionar**: reorganize o array para que elementos menores que o pivô fiquem à esquerda e maiores à direita 3. **Recursão**: aplique Quick Sort nas duas partições ### Visualização do Processo ``` Array: [10, 80, 30, 90, 40, 50, 70] pivô = 70 Particionamento (Lomuto): i aponta para onde colocar o próximo menor que pivô [10, 80, 30, 90, 40, 50, 70] 10<70 → troca posição 0 com 0: [10, 80, 30, 90, 40, 50, 70] 80>70 → nada 30<70 → troca posição 1 com 2: [10, 30, 80, 90, 40, 50, 70] 90>70 → nada 40<70 → troca posição 2 com 4: [10, 30, 40, 90, 80, 50, 70] 50<70 → troca posição 3 com 5: [10, 30, 40, 50, 80, 90, 70] Coloca pivô na posição 4: [10, 30, 40, 50, 70, 90, 80] ↑ menores ↑ ↑ maiores ↑ Recursão nas duas partições: [10, 30, 40, 50] e [90, 80] ... continua até partições de tamanho 1 ``` ## Implementação em Zig ```zig const std = @import("std"); /// Quick Sort usando particionamento de Lomuto. pub fn quickSort(comptime T: type, items: []T) void { if (items.len <= 1) return; quickSortHelper(T, items, 0, items.len - 1); } fn quickSortHelper(comptime T: type, items: []T, low: usize, high: usize) void { if (low >= high) return; const pivot_idx = partitionLomuto(T, items, low, high); // Recursão nas partições if (pivot_idx > 0) quickSortHelper(T, items, low, pivot_idx - 1); if (pivot_idx < items.len - 1) quickSortHelper(T, items, pivot_idx + 1, high); } /// Particionamento de Lomuto: usa o último elemento como pivô. fn partitionLomuto(comptime T: type, items: []T, low: usize, high: usize) usize { const pivot = items[high]; var i: usize = low; var j: usize = low; while (j < high) : (j += 1) { if (items[j] <= pivot) { const temp = items[i]; items[i] = items[j]; items[j] = temp; i += 1; } } // Coloca o pivô na posição correta const temp = items[i]; items[i] = items[high]; items[high] = temp; return i; } /// Quick Sort com particionamento de Hoare (mais eficiente). pub fn quickSortHoare(comptime T: type, items: []T) void { if (items.len <= 1) return; quickSortHoareHelper(T, items, 0, items.len - 1); } fn quickSortHoareHelper(comptime T: type, items: []T, low: usize, high: usize) void { if (low >= high) return; const p = partitionHoare(T, items, low, high); if (p > 0) quickSortHoareHelper(T, items, low, p); quickSortHoareHelper(T, items, p + 1, high); } /// Particionamento de Hoare: dois ponteiros convergindo ao centro. fn partitionHoare(comptime T: type, items: []T, low: usize, high: usize) usize { const pivot = items[low + (high - low) / 2]; var i: usize = if (low > 0) low - 1 else 0; var j: usize = high + 1; if (low == 0) { i = 0; // Ajuste especial para quando low é 0 while (true) { j -= 1; while (items[j] > pivot) : (j -= 1) {} while (items[i] < pivot) : (i += 1) {} if (i >= j) return j; const temp = items[i]; items[i] = items[j]; items[j] = temp; i += 1; } } while (true) { i += 1; while (items[i] < pivot) : (i += 1) {} j -= 1; while (items[j] > pivot) : (j -= 1) {} if (i >= j) return j; const temp = items[i]; items[i] = items[j]; items[j] = temp; } } /// Quick Sort com mediana de três como pivô (anti pior caso). pub fn quickSortMediana3(comptime T: type, items: []T) void { if (items.len <= 1) return; qsMediana3(T, items, 0, items.len - 1); } fn qsMediana3(comptime T: type, items: []T, low: usize, high: usize) void { if (high <= low) return; // Para partições pequenas, usa insertion sort if (high - low < 10) { var i: usize = low + 1; while (i <= high) : (i += 1) { const chave = items[i]; var j: usize = i; while (j > low and items[j - 1] > chave) { items[j] = items[j - 1]; j -= 1; } items[j] = chave; } return; } // Mediana de três: primeiro, meio, último const meio = low + (high - low) / 2; if (items[meio] < items[low]) { const t = items[low]; items[low] = items[meio]; items[meio] = t; } if (items[high] < items[low]) { const t = items[low]; items[low] = items[high]; items[high] = t; } if (items[high] < items[meio]) { const t = items[meio]; items[meio] = items[high]; items[high] = t; } // Mediana está em items[meio], move para high-1 const t = items[meio]; items[meio] = items[high - 1]; items[high - 1] = t; const pivot_idx = partitionLomuto(T, items, low, high - 1); if (pivot_idx > 0) qsMediana3(T, items, low, pivot_idx - 1); if (pivot_idx < items.len - 1) qsMediana3(T, items, pivot_idx + 1, high); } pub fn main() !void { const stdout = std.io.getStdOut().writer(); var numeros = [_]i32{ 10, 80, 30, 90, 40, 50, 70 }; try stdout.print("Original: ", .{}); for (numeros) |n| try stdout.print("{d} ", .{n}); try stdout.print("\n", .{}); quickSort(i32, &numeros); try stdout.print("Ordenado: ", .{}); for (numeros) |n| try stdout.print("{d} ", .{n}); try stdout.print("\n", .{}); } ``` ## Análise de Complexidade | Caso | Tempo | Espaço | |------|-------|--------| | **Melhor caso** | O(n log n) — pivô divide ao meio | O(log n) recursão | | **Caso médio** | O(n log n) | O(log n) | | **Pior caso** | O(n²) — array já ordenado com pivô fixo | O(n) recursão | ### Evitando o Pior Caso O pior caso ocorre quando o pivô é sempre o menor ou maior elemento. Estratégias para evitar: - **Mediana de três**: escolhe a mediana entre primeiro, meio e último - **Pivô aleatório**: escolhe aleatoriamente - **Insertion sort para partições pequenas**: evita overhead de recursão ## Características - **Estável**: Não — o particionamento pode trocar elementos iguais - **In-place**: Sim — O(log n) na pilha de recursão - **Cache-friendly**: Sim — acessa memória sequencialmente - **Na prática**: Geralmente o mais rápido dos O(n log n) ## Quick Sort vs Merge Sort | Aspecto | Quick Sort | [Merge Sort](/algoritmos/merge-sort/) | |---------|-----------|-----------| | Melhor caso | O(n log n) | O(n log n) | | Pior caso | O(n²) | O(n log n) | | Espaço | O(log n) | O(n) | | Estável | Não | Sim | | Cache | Excelente | Bom | | Prática | Geralmente mais rápido | Mais previsível | ## Recursos Relacionados - [Merge Sort em Zig](/algoritmos/merge-sort/) — Alternativa estável O(n log n) - [Heap Sort em Zig](/algoritmos/heap-sort/) — O(n log n) garantido e in-place - [Insertion Sort em Zig](/algoritmos/insertion-sort/) — Usado como otimização para partições pequenas - [Two Pointers](/algoritmos/two-pointers/) — Técnica similar ao particionamento de Hoare - [Array Dinâmico](/estruturas-dados/array-dinamico/) — Estrutura base para ordenação