--- title: "Selection Sort em Rust" url: "https://rustlang.com.br/algoritmos/selection-sort/" markdown_url: "https://rustlang.com.br/algoritmos/selection-sort.MD" description: "Aprenda Selection Sort em Rust com diagramas visuais, análise Big-O, código genérico completo e comparações. Guia em português." date: "2026-02-24" author: "Equipe Rust Brasil" --- # Selection Sort em Rust Aprenda Selection Sort em Rust com diagramas visuais, análise Big-O, código genérico completo e comparações. Guia em português. O **Selection Sort** (ordenação por seleção) é um algoritmo de ordenação simples que funciona de maneira intuitiva: a cada iteração, ele encontra o menor elemento da parte não ordenada do vetor e o coloca na próxima posição da parte ordenada. É como organizar cartas na mão — você procura a menor, coloca na frente, procura a próxima menor, coloca em seguida, e assim por diante. Apesar de ter complexidade O(n²) como o Bubble Sort, o Selection Sort tem uma vantagem importante: realiza no máximo **n-1 trocas**, o que o torna interessante quando o custo de trocar elementos é alto (por exemplo, quando os elementos são structs grandes). No entanto, ele é um algoritmo **instável** — elementos com valores iguais podem ter sua ordem relativa alterada. ## Como Funciona O algoritmo divide logicamente o vetor em duas partes: a parte ordenada (à esquerda) e a parte não ordenada (à direita). A cada passo, ele seleciona o menor elemento da parte não ordenada e o troca com o primeiro elemento da parte não ordenada. ```text Vetor inicial: [29, 10, 14, 37, 13] |--- não ordenado ---| === Passo 1: encontrar o mínimo em [29, 10, 14, 37, 13] === Mínimo = 10 (posição 1) Trocar posição 0 ↔ posição 1 [10, 29, 14, 37, 13] ✓ |--- não ordenado --| === Passo 2: encontrar o mínimo em [29, 14, 37, 13] === Mínimo = 13 (posição 4) Trocar posição 1 ↔ posição 4 [10, 13, 14, 37, 29] ✓ ✓ |-- não ord --| === Passo 3: encontrar o mínimo em [14, 37, 29] === Mínimo = 14 (posição 2) — já está no lugar! Sem troca necessária [10, 13, 14, 37, 29] ✓ ✓ ✓ |não ord| === Passo 4: encontrar o mínimo em [37, 29] === Mínimo = 29 (posição 4) Trocar posição 3 ↔ posição 4 [10, 13, 14, 29, 37] ✓ ✓ ✓ ✓ ✓ Resultado: [10, 13, 14, 29, 37] ``` Visualmente, o processo de seleção em cada passo: ```text Passo 1: [29 10 14 37 13] busca mínimo: 10 ~~ ^^ Passo 2: [10 |29 14 37 13] busca mínimo: 13 ~~ ^^ Passo 3: [10 13 |14 37 29] busca mínimo: 14 ^^ (no lugar) Passo 4: [10 13 14 |37 29] busca mínimo: 29 ~~ ^^ Final: [10 13 14 29 37] ✓ ordenado! Legenda: ~~ = posição atual | ^^ = mínimo encontrado | | = fronteira ordenado/não-ordenado ``` ## Complexidade | Caso | Tempo | Espaço | |------|-------|--------| | Melhor | O(n²) | O(1) | | Médio | O(n²) | O(1) | | Pior | O(n²) | O(1) | - **Todos os casos O(n²):** independente da ordem inicial, o Selection Sort sempre faz o mesmo número de comparações: n(n-1)/2. Ele não é adaptativo — não se beneficia de dados parcialmente ordenados. - **Espaço O(1):** é um algoritmo **in-place** que usa apenas uma variável para armazenar o índice do mínimo. - **Número de trocas O(n):** esta é a principal vantagem do Selection Sort. Ele faz no máximo n-1 trocas, enquanto Bubble Sort e Insertion Sort podem fazer O(n²) trocas. ## Implementação em Rust ```rust /// Selection Sort genérico. /// Ordena o slice in-place em ordem crescente. /// Requer que os elementos implementem `PartialOrd`. fn selection_sort(vetor: &mut [T]) { let n = vetor.len(); for i in 0..n.saturating_sub(1) { // Encontrar o índice do menor elemento na parte não ordenada let mut indice_minimo = i; for j in (i + 1)..n { if vetor[j] < vetor[indice_minimo] { indice_minimo = j; } } // Trocar apenas se o mínimo não estiver na posição correta if indice_minimo != i { vetor.swap(i, indice_minimo); } } } fn main() { // Exemplo com inteiros let mut numeros = vec![29, 10, 14, 37, 13]; println!("Antes: {:?}", numeros); selection_sort(&mut numeros); println!("Depois: {:?}", numeros); // Exemplo com caracteres let mut letras = vec!['r', 'u', 's', 't', 'a']; println!("\nAntes: {:?}", letras); selection_sort(&mut letras); println!("Depois: {:?}", letras); // Exemplo com array fixo (slice) let mut arr = [64, 25, 12, 22, 11]; println!("\nAntes: {:?}", arr); selection_sort(&mut arr); println!("Depois: {:?}", arr); } ``` ## Exemplo de Execução ```text Antes: [29, 10, 14, 37, 13] Depois: [10, 13, 14, 29, 37] Antes: ['r', 'u', 's', 't', 'a'] Depois: ['a', 'r', 's', 't', 'u'] Antes: [64, 25, 12, 22, 11] Depois: [11, 12, 22, 25, 64] ``` Versão com rastreamento passo a passo: ```rust fn selection_sort_rastreado(vetor: &mut Vec) { let n = vetor.len(); for i in 0..n.saturating_sub(1) { let mut indice_minimo = i; for j in (i + 1)..n { if vetor[j] < vetor[indice_minimo] { indice_minimo = j; } } println!( "Passo {}: mínimo = {} (pos {}), vetor antes = {:?}", i + 1, vetor[indice_minimo], indice_minimo, vetor ); if indice_minimo != i { vetor.swap(i, indice_minimo); println!(" troca pos {} ↔ pos {} → {:?}", i, indice_minimo, vetor); } else { println!(" já está no lugar correto"); } } } fn main() { let mut v = vec![29, 10, 14, 37, 13]; println!("Entrada: {:?}\n", v); selection_sort_rastreado(&mut v); println!("\nResultado: {:?}", v); } ``` ## Variações e Otimizações ### 1. Double Selection Sort (Seleção Dupla) Em cada passagem, encontramos tanto o mínimo quanto o máximo, colocando-os nas posições corretas simultaneamente. Isso reduz o número de passagens pela metade. ```rust /// Double Selection Sort — encontra mínimo e máximo simultaneamente. fn double_selection_sort(vetor: &mut [T]) { let n = vetor.len(); if n <= 1 { return; } let mut esquerda = 0; let mut direita = n - 1; while esquerda < direita { let mut indice_min = esquerda; let mut indice_max = esquerda; for i in esquerda..=direita { if vetor[i] < vetor[indice_min] { indice_min = i; } if vetor[i] > vetor[indice_max] { indice_max = i; } } // Colocar o mínimo na posição esquerda vetor.swap(esquerda, indice_min); // Se o máximo estava na posição esquerda, ele foi movido // para onde o mínimo estava if indice_max == esquerda { indice_max = indice_min; } // Colocar o máximo na posição direita vetor.swap(direita, indice_max); esquerda += 1; direita -= 1; } } fn main() { let mut v = vec![29, 10, 14, 37, 13, 5, 42, 8]; println!("Antes: {:?}", v); double_selection_sort(&mut v); println!("Depois: {:?}", v); } ``` ### 2. Selection Sort com Iteradores Rust Usando a API de iteradores do Rust para encontrar o mínimo de forma mais idiomática: ```rust /// Selection Sort usando iteradores para encontrar o mínimo. fn selection_sort_idiomatico(vetor: &mut [T]) { let n = vetor.len(); for i in 0..n.saturating_sub(1) { // Usar enumerate e min_by para encontrar o índice do mínimo if let Some((indice_relativo, _)) = vetor[i..] .iter() .enumerate() .min_by(|(_, a), (_, b)| a.cmp(b)) { let indice_absoluto = i + indice_relativo; if indice_absoluto != i { vetor.swap(i, indice_absoluto); } } } } fn main() { let mut v = vec![5, 2, 9, 1, 7, 3]; selection_sort_idiomatico(&mut v); println!("Ordenado: {:?}", v); } ``` ### 3. Selection Sort Estável O Selection Sort padrão é instável. Podemos torná-lo estável usando inserção em vez de troca, mas isso aumenta o número de movimentações: ```rust /// Selection Sort estável — usa rotação em vez de troca. fn stable_selection_sort(vetor: &mut [T]) { let n = vetor.len(); for i in 0..n.saturating_sub(1) { let mut indice_minimo = i; for j in (i + 1)..n { if vetor[j] < vetor[indice_minimo] { indice_minimo = j; } } // Em vez de trocar, rotacionar os elementos entre i e indice_minimo // Isso preserva a ordem relativa dos elementos iguais if indice_minimo != i { // Rotacionar: mover o mínimo para a posição i // deslocando todos os intermediários uma posição à direita let mut pos = indice_minimo; while pos > i { vetor.swap(pos, pos - 1); pos -= 1; } } } } fn main() { let mut v = vec![3, 1, 4, 1, 5, 9, 2, 6]; stable_selection_sort(&mut v); println!("Estável: {:?}", v); } ``` ## Quando Usar O Selection Sort é indicado nos seguintes cenários: - **Custo de troca alto:** quando trocar dois elementos é caro (structs grandes em memória), o Selection Sort é vantajoso por fazer no máximo O(n) trocas, contra O(n²) do Bubble Sort e Insertion Sort. - **Memória restrita:** por ser in-place com O(1) de espaço extra, funciona em sistemas com memória muito limitada. - **Fins educacionais:** excelente para ensinar o conceito de "encontrar o mínimo" e a divisão em subproblemas. - **Verificação de implementação:** por ter comportamento completamente previsível (sempre n(n-1)/2 comparações), é útil para verificar outras implementações. **Evite** o Selection Sort quando: - O vetor estiver parcialmente ordenado — o [Insertion Sort](/algoritmos/insertion-sort/) se beneficia dessa situação, o Selection Sort não. - Estabilidade for necessária — o Selection Sort padrão é instável. - O volume de dados for grande — prefira [Merge Sort](/algoritmos/merge-sort/) ou [Quick Sort](/algoritmos/quick-sort/). ## Comparação com Outros Algoritmos | Característica | Selection Sort | [Bubble Sort](/algoritmos/bubble-sort/) | [Insertion Sort](/algoritmos/insertion-sort/) | |---|---|---|---| | Complexidade (média) | O(n²) | O(n²) | O(n²) | | Melhor caso | O(n²) | O(n) ✓ | O(n) ✓ | | Estável | Não ✗ | Sim ✓ | Sim ✓ | | Adaptativo | Não ✗ | Sim ✓ | Sim ✓ | | Trocas (média) | O(n) ✓ | O(n²) | O(n²) | | In-place | Sim | Sim | Sim | | Melhor para | Trocas caras | Educacional | Quase ordenados | O ponto forte do Selection Sort é o **número mínimo de trocas**. Quando o custo de mover dados é alto (por exemplo, registros em memória lenta), essa vantagem pode superar a falta de adaptatividade. No entanto, na maioria dos cenários práticos, o Insertion Sort é a melhor escolha entre os algoritmos O(n²). ## Exercícios Práticos 1. **Encontrar os k menores:** Modifique o Selection Sort para encontrar apenas os `k` menores elementos de um vetor, parando após `k` iterações. Qual é a complexidade dessa versão em termos de `n` e `k`? 2. **Selection Sort com comparador:** Implemente uma versão que aceite uma closure de comparação `F: Fn(&T, &T) -> std::cmp::Ordering`, permitindo ordenação personalizada. Teste ordenando uma lista de tuplas `(String, u32)` por diferentes campos. 3. **Análise de estabilidade:** Crie um vetor de pares `(valor, indice_original)` com valores repetidos. Ordene com Selection Sort e Insertion Sort. Verifique se a ordem relativa dos elementos com mesmo valor é preservada em cada caso. Explique a diferença. 4. **Medição de desempenho:** Compare Selection Sort, Bubble Sort e Insertion Sort em três cenários: vetor aleatório, vetor quase ordenado (90% em ordem) e vetor em ordem reversa. Use `std::time::Instant` para medir o tempo. Qual algoritmo se sai melhor em cada cenário? ## Veja Também - [Bubble Sort em Rust](/algoritmos/bubble-sort/) — algoritmo O(n²) com propriedade de saída antecipada - [Insertion Sort em Rust](/algoritmos/insertion-sort/) — alternativa O(n²) adaptativa e estável - [Heap Sort em Rust](/algoritmos/heap-sort/) — versão aprimorada do conceito de "seleção do mínimo" usando heap - [Vec — Vetores Dinâmicos](/stdlib/vec/) — estrutura de dados fundamental para ordenação - [Slice — Fatias de Memória](/stdlib/slice/) — métodos `swap()`, `sort()` e `sort_unstable()` - [Iterator — Iteradores](/stdlib/iterator/) — métodos `min()`, `min_by()` e `enumerate()`