Selection Sort em Zig — Implementação e Explicação
O Selection Sort (ordenação por seleção) é um algoritmo de ordenação simples que funciona dividindo o array em duas partes: a porção já ordenada (à esquerda) e a porção não ordenada (à direita). A cada iteração, o algoritmo seleciona o menor elemento da porção não ordenada e o coloca na posição correta.
Como Funciona
- Encontre o menor elemento no array inteiro
- Troque-o com o primeiro elemento
- Encontre o menor elemento no subarray restante (excluindo o primeiro)
- Troque-o com o segundo elemento
- Repita até que todo o array esteja ordenado
Visualização do Processo
Array inicial: [29, 10, 14, 37, 13]
↑ parte ordenada | parte não ordenada
Passo 1: menor = 10 (posição 1) → troca com posição 0
[10 | 29, 14, 37, 13]
✓
Passo 2: menor = 13 (posição 4) → troca com posição 1
[10, 13 | 14, 37, 29]
✓ ✓
Passo 3: menor = 14 (posição 2) → já na posição certa
[10, 13, 14 | 37, 29]
✓ ✓ ✓
Passo 4: menor = 29 (posição 4) → troca com posição 3
[10, 13, 14, 29 | 37]
✓ ✓ ✓ ✓
Resultado: [10, 13, 14, 29, 37] ✓
Implementação em Zig
const std = @import("std");
/// Selection Sort genérico para slices de qualquer tipo comparável.
/// Ordena o slice in-place em ordem crescente.
pub fn selectionSort(comptime T: type, items: []T) void {
const len = items.len;
if (len <= 1) return;
var i: usize = 0;
while (i < len - 1) : (i += 1) {
// Encontra o índice do menor elemento na parte não ordenada
var min_idx: usize = i;
var j: usize = i + 1;
while (j < len) : (j += 1) {
if (items[j] < items[min_idx]) {
min_idx = j;
}
}
// Troca o menor encontrado com o elemento na posição i
if (min_idx != i) {
const temp = items[i];
items[i] = items[min_idx];
items[min_idx] = temp;
}
}
}
/// Versão com função de comparação personalizada
pub fn selectionSortBy(
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 min_idx: usize = i;
var j: usize = i + 1;
while (j < len) : (j += 1) {
if (lessThan(items[j], items[min_idx])) {
min_idx = j;
}
}
if (min_idx != i) {
const temp = items[i];
items[i] = items[min_idx];
items[min_idx] = temp;
}
}
}
pub fn main() !void {
const stdout = std.io.getStdOut().writer();
var numeros = [_]i32{ 64, 25, 12, 22, 11 };
try stdout.print("Array original: ", .{});
for (numeros) |n| try stdout.print("{d} ", .{n});
try stdout.print("\n", .{});
selectionSort(i32, &numeros);
try stdout.print("Array ordenado: ", .{});
for (numeros) |n| try stdout.print("{d} ", .{n});
try stdout.print("\n", .{});
// Exemplo com floats em ordem decrescente
var floats = [_]f64{ 3.14, 1.41, 2.72, 0.58, 1.73 };
selectionSortBy(f64, &floats, struct {
fn f(a: f64, b: f64) bool {
return a > b;
}
}.f);
try stdout.print("Floats decrescente: ", .{});
for (floats) |n| try stdout.print("{d:.2} ", .{n});
try stdout.print("\n", .{});
}
Análise de Complexidade
| Caso | Tempo | Espaço |
|---|---|---|
| Melhor caso | O(n²) | O(1) |
| Caso médio | O(n²) | O(1) |
| Pior caso | O(n²) | O(1) |
Por que sempre O(n²)?
Diferente do Bubble Sort, o Selection Sort não tem otimização para arrays já ordenados. Ele sempre precisa percorrer toda a parte não ordenada para encontrar o mínimo, resultando em n + (n-1) + (n-2) + ... + 1 = n(n-1)/2 comparações.
A vantagem é que faz no máximo n-1 trocas, muito menos que o Bubble Sort que pode fazer O(n²) trocas. Isso é útil quando o custo de trocar elementos é alto.
Características
- Estável: Não — a troca pode alterar a ordem de elementos iguais
- In-place: Sim — usa apenas O(1) de memória adicional
- Adaptativo: Não — sempre faz O(n²) comparações
- Número de trocas: O(n) — vantagem quando trocas são custosas
Quando Usar
O Selection Sort é adequado para:
- Arrays pequenos: a simplicidade compensa para poucos elementos
- Trocas custosas: faz o mínimo de trocas (no máximo n-1)
- Fins educacionais: fácil de entender e implementar
Para listas maiores, prefira algoritmos com complexidade O(n log n) como Merge Sort ou Quick Sort.
Variante: Seleção Dupla
Uma otimização possível é encontrar tanto o menor quanto o maior elemento em cada passagem, reduzindo o número de passagens pela metade:
pub fn doubleSelectionSort(comptime T: type, items: []T) void {
const len = items.len;
if (len <= 1) return;
var esquerda: usize = 0;
var direita: usize = len - 1;
while (esquerda < direita) {
var min_idx: usize = esquerda;
var max_idx: usize = esquerda;
var i: usize = esquerda;
while (i <= direita) : (i += 1) {
if (items[i] < items[min_idx]) min_idx = i;
if (items[i] > items[max_idx]) max_idx = i;
}
// Troca o mínimo para a esquerda
const temp_min = items[esquerda];
items[esquerda] = items[min_idx];
items[min_idx] = temp_min;
// Ajusta max_idx se foi afetado pela troca anterior
if (max_idx == esquerda) max_idx = min_idx;
// Troca o máximo para a direita
const temp_max = items[direita];
items[direita] = items[max_idx];
items[max_idx] = temp_max;
esquerda += 1;
direita -= 1;
}
}
Recursos Relacionados
- Bubble Sort em Zig — Algoritmo simples por troca de adjacentes
- Insertion Sort em Zig — Melhor alternativa para listas pequenas
- Heap Sort em Zig — Versão otimizada da ideia de seleção
- Array Estático em Zig — Estrutura base para ordenação
- Heap Binário — Estrutura que otimiza a seleção do mínimo