Selection Sort em Rust

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.

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:

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

/// Selection Sort genérico.
/// Ordena o slice in-place em ordem crescente.
/// Requer que os elementos implementem `PartialOrd`.
fn selection_sort<T: PartialOrd>(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

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:

fn selection_sort_rastreado(vetor: &mut Vec<i32>) {
    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.

/// Double Selection Sort — encontra mínimo e máximo simultaneamente.
fn double_selection_sort<T: PartialOrd>(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:

/// Selection Sort usando iteradores para encontrar o mínimo.
fn selection_sort_idiomatico<T: Ord>(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:

/// Selection Sort estável — usa rotação em vez de troca.
fn stable_selection_sort<T: PartialOrd>(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 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 ou Quick Sort.

Comparação com Outros Algoritmos

Característica	Selection Sort	Bubble Sort	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

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?
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.
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.
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 — algoritmo O(n²) com propriedade de saída antecipada
Insertion Sort em Rust — alternativa O(n²) adaptativa e estável
Heap Sort em Rust — versão aprimorada do conceito de “seleção do mínimo” usando heap
Vec — Vetores Dinâmicos — estrutura de dados fundamental para ordenação
Slice — Fatias de Memória — métodos swap(), sort() e sort_unstable()
Iterator — Iteradores — métodos min(), min_by() e enumerate()