Insertion Sort em Rust

O Insertion Sort (ordenação por inserção) é um algoritmo de ordenação simples que constrói a sequência ordenada um elemento por vez. Sua lógica é similar à forma como a maioria das pessoas organiza cartas na mão: você pega uma carta de cada vez e a insere na posição correta entre as cartas já organizadas.

Entre os algoritmos O(n²), o Insertion Sort é o mais utilizado na prática. Ele é estável, adaptativo (aproveita dados parcialmente ordenados) e tem excelente desempenho para vetores pequenos. Não é coincidência que algoritmos de ordenação sofisticados como o TimSort (usado em Python e Java) e o sort() da biblioteca padrão do Rust utilizem o Insertion Sort como caso base para partições pequenas.

Como Funciona

O algoritmo percorre o vetor da esquerda para a direita. Para cada elemento, ele o compara com os elementos anteriores (já ordenados) e o desloca para a posição correta, movendo os maiores uma posição à direita.

Vetor inicial: [7, 3, 5, 1, 9, 2]

=== Passo 1: inserir o 3 ===
  Parte ordenada: [7]  |  Elemento: 3
  3 < 7 → desloca 7 para a direita
  Insere 3 na posição 0
  [3, 7, 5, 1, 9, 2]
   ✓  ✓

=== Passo 2: inserir o 5 ===
  Parte ordenada: [3, 7]  |  Elemento: 5
  5 < 7 → desloca 7 para a direita
  5 > 3 → posição encontrada!
  Insere 5 na posição 1
  [3, 5, 7, 1, 9, 2]
   ✓  ✓  ✓

=== Passo 3: inserir o 1 ===
  Parte ordenada: [3, 5, 7]  |  Elemento: 1
  1 < 7 → desloca 7
  1 < 5 → desloca 5
  1 < 3 → desloca 3
  Insere 1 na posição 0
  [1, 3, 5, 7, 9, 2]
   ✓  ✓  ✓  ✓

=== Passo 4: inserir o 9 ===
  Parte ordenada: [1, 3, 5, 7]  |  Elemento: 9
  9 > 7 → já está na posição correta!
  [1, 3, 5, 7, 9, 2]
   ✓  ✓  ✓  ✓  ✓

=== Passo 5: inserir o 2 ===
  Parte ordenada: [1, 3, 5, 7, 9]  |  Elemento: 2
  2 < 9 → desloca 9
  2 < 7 → desloca 7
  2 < 5 → desloca 5
  2 < 3 → desloca 3
  2 > 1 → posição encontrada!
  Insere 2 na posição 1
  [1, 2, 3, 5, 7, 9]
   ✓  ✓  ✓  ✓  ✓  ✓

Resultado: [1, 2, 3, 5, 7, 9]

Diagrama visual do deslocamento (shift) no passo 5:

  Inserindo o 2 na parte ordenada [1, 3, 5, 7, 9]:

  [1, 3, 5, 7, 9, _]     salvar 2 em variável temporária

  [1, 3, 5, 7, _, 9]     desloca 9 →
  [1, 3, 5, _, 7, 9]     desloca 7 →
  [1, 3, _, 5, 7, 9]     desloca 5 →
  [1, _, 3, 5, 7, 9]     desloca 3 →
  [1, 2, 3, 5, 7, 9]     insere 2 na posição vazia

Complexidade

Caso	Tempo	Espaço
Melhor	O(n)	O(1)
Médio	O(n²)	O(1)
Pior	O(n²)	O(1)

Melhor caso O(n): quando o vetor já está ordenado, cada elemento é comparado apenas uma vez com o anterior, totalizando n-1 comparações e zero deslocamentos.
Caso médio O(n²): para dados aleatórios, cada elemento é inserido aproximadamente na metade da parte ordenada, resultando em ~n²/4 comparações e deslocamentos.
Pior caso O(n²): ocorre quando o vetor está em ordem decrescente. Cada novo elemento precisa ser movido para o início, resultando em ~n²/2 comparações e deslocamentos.
Espaço O(1): algoritmo in-place, utiliza apenas uma variável temporária.

Propriedade adaptativa: o Insertion Sort executa em O(n + d), onde d é o número de inversões no vetor. Para vetores quase ordenados (poucas inversões), o desempenho se aproxima de O(n).

Implementação em Rust

/// Insertion Sort genérico.
/// Ordena o slice in-place em ordem crescente.
/// Algoritmo estável e adaptativo.
fn insertion_sort<T: PartialOrd>(vetor: &mut [T]) {
    let n = vetor.len();

    for i in 1..n {
        // O elemento na posição `i` precisa ser inserido
        // na posição correta dentro de vetor[0..i]
        let mut j = i;

        // Desloca elementos maiores para a direita
        while j > 0 && vetor[j - 1] > vetor[j] {
            vetor.swap(j - 1, j);
            j -= 1;
        }
    }
}

fn main() {
    // Exemplo com inteiros
    let mut numeros = vec![7, 3, 5, 1, 9, 2];
    println!("Antes:  {:?}", numeros);
    insertion_sort(&mut numeros);
    println!("Depois: {:?}", numeros);

    // Exemplo com strings
    let mut nomes = vec!["Rust", "Python", "Go", "C", "Java"];
    println!("\nAntes:  {:?}", nomes);
    insertion_sort(&mut nomes);
    println!("Depois: {:?}", nomes);

    // Exemplo com vetor quase ordenado (caso ideal)
    let mut quase = vec![1, 2, 4, 3, 5, 6, 8, 7];
    println!("\nAntes:  {:?}", quase);
    insertion_sort(&mut quase);
    println!("Depois: {:?}", quase);
}

Exemplo de Execução

Antes:  [7, 3, 5, 1, 9, 2]
Depois: [1, 2, 3, 5, 7, 9]

Antes:  ["Rust", "Python", "Go", "C", "Java"]
Depois: ["C", "Go", "Java", "Python", "Rust"]

Antes:  [1, 2, 4, 3, 5, 6, 8, 7]
Depois: [1, 2, 3, 4, 5, 6, 7, 8]

Versão com rastreamento detalhado:

fn insertion_sort_rastreado(vetor: &mut Vec<i32>) {
    let n = vetor.len();

    for i in 1..n {
        let valor = vetor[i];
        let mut j = i;
        let mut deslocamentos = 0;

        while j > 0 && vetor[j - 1] > vetor[j] {
            vetor.swap(j - 1, j);
            j -= 1;
            deslocamentos += 1;
        }

        println!(
            "Passo {}: inserir {} → posição {} ({} deslocamentos) → {:?}",
            i, valor, j, deslocamentos, vetor
        );
    }
}

fn main() {
    let mut v = vec![7, 3, 5, 1, 9, 2];
    println!("Entrada: {:?}\n", v);
    insertion_sort_rastreado(&mut v);
    println!("\nResultado: {:?}", v);
}

Saída esperada:

Entrada: [7, 3, 5, 1, 9, 2]

Passo 1: inserir 3 → posição 0 (1 deslocamentos) → [3, 7, 5, 1, 9, 2]
Passo 2: inserir 5 → posição 1 (1 deslocamentos) → [3, 5, 7, 1, 9, 2]
Passo 3: inserir 1 → posição 0 (3 deslocamentos) → [1, 3, 5, 7, 9, 2]
Passo 4: inserir 9 → posição 4 (0 deslocamentos) → [1, 3, 5, 7, 9, 2]
Passo 5: inserir 2 → posição 1 (4 deslocamentos) → [1, 2, 3, 5, 7, 9]

Resultado: [1, 2, 3, 5, 7, 9]

Variações e Otimizações

1. Insertion Sort com Busca Binária

Podemos usar busca binária para encontrar a posição de inserção, reduzindo o número de comparações de O(n) para O(log n) por elemento. Porém, o número de deslocamentos continua O(n), então a complexidade total permanece O(n²).

/// Insertion Sort com busca binária para encontrar posição de inserção.
/// Reduz comparações, mas mantém O(n²) por causa dos deslocamentos.
fn binary_insertion_sort<T: Ord>(vetor: &mut [T]) {
    let n = vetor.len();

    for i in 1..n {
        // Usar busca binária para encontrar a posição de inserção
        // partition_point retorna o índice onde o elemento deve ser inserido
        let pos = vetor[..i].partition_point(|x| x < &vetor[i]);

        // Rotacionar os elementos para abrir espaço
        // rotate_right move os elementos para a direita
        vetor[pos..=i].rotate_right(1);
    }
}

fn main() {
    let mut v = vec![7, 3, 5, 1, 9, 2];
    println!("Antes:  {:?}", v);
    binary_insertion_sort(&mut v);
    println!("Depois: {:?}", v);

    // Comparação: ambos produzem o mesmo resultado
    let mut v2 = vec![50, 20, 40, 10, 30];
    println!("\nAntes:  {:?}", v2);
    binary_insertion_sort(&mut v2);
    println!("Depois: {:?}", v2);
}

2. Shell Sort (Insertion Sort com Gap)

O Shell Sort é uma generalização do Insertion Sort que compara e troca elementos distantes, reduzindo progressivamente a distância (gap) até chegar a 1, quando se torna um Insertion Sort padrão sobre dados quase ordenados.

/// Shell Sort — Insertion Sort com gap decrescente.
/// Usa a sequência de gaps de Knuth: 1, 4, 13, 40, 121, ...
fn shell_sort<T: PartialOrd>(vetor: &mut [T]) {
    let n = vetor.len();

    // Calcular o maior gap da sequência de Knuth
    let mut gap = 1;
    while gap < n / 3 {
        gap = gap * 3 + 1; // 1, 4, 13, 40, 121, ...
    }

    while gap >= 1 {
        // Insertion Sort com o gap atual
        for i in gap..n {
            let mut j = i;
            while j >= gap && vetor[j - gap] > vetor[j] {
                vetor.swap(j - gap, j);
                j -= gap;
            }
        }
        gap /= 3;
    }
}

fn main() {
    let mut v = vec![35, 33, 42, 10, 14, 19, 27, 44, 26, 31];
    println!("Antes:  {:?}", v);
    shell_sort(&mut v);
    println!("Depois: {:?}", v);
}

3. Insertion Sort como Caso Base em Algoritmos Híbridos

Na prática, o Insertion Sort é usado como caso base quando o tamanho da partição fica pequeno em algoritmos como Quick Sort e Merge Sort. Isso explora o fato de que o Insertion Sort tem menor overhead que algoritmos recursivos para poucos elementos.

/// Exemplo de como Insertion Sort é usado como caso base.
/// Ordena a sub-fatia usando Insertion Sort quando o tamanho é pequeno.
fn insertion_sort_faixa<T: PartialOrd>(vetor: &mut [T], inicio: usize, fim: usize) {
    for i in (inicio + 1)..=fim {
        let mut j = i;
        while j > inicio && vetor[j - 1] > vetor[j] {
            vetor.swap(j - 1, j);
            j -= 1;
        }
    }
}

/// Quick Sort híbrido que usa Insertion Sort para partições pequenas.
const LIMIAR_INSERCAO: usize = 16;

fn quick_sort_hibrido<T: PartialOrd>(vetor: &mut [T]) {
    quick_sort_interno(vetor, 0, vetor.len().saturating_sub(1));
}

fn quick_sort_interno<T: PartialOrd>(vetor: &mut [T], inicio: usize, fim: usize) {
    if inicio >= fim {
        return;
    }

    // Para partições pequenas, usar Insertion Sort
    if fim - inicio + 1 <= LIMIAR_INSERCAO {
        insertion_sort_faixa(vetor, inicio, fim);
        return;
    }

    // Particionamento simples (Lomuto)
    let pivo_pos = fim;
    let mut i = inicio;
    for j in inicio..fim {
        if vetor[j] <= vetor[pivo_pos] {
            vetor.swap(i, j);
            i += 1;
        }
    }
    vetor.swap(i, pivo_pos);

    if i > 0 {
        quick_sort_interno(vetor, inicio, i.saturating_sub(1));
    }
    quick_sort_interno(vetor, i + 1, fim);
}

fn main() {
    let mut v = vec![38, 27, 43, 3, 9, 82, 10, 15, 7, 1, 45, 22, 5, 19, 33, 12, 50, 41, 8, 6];
    println!("Antes:  {:?}", v);
    quick_sort_hibrido(&mut v);
    println!("Depois: {:?}", v);
}

Quando Usar

O Insertion Sort e a escolha ideal nos seguintes cenarios:

Vetores pequenos (n < 50): o baixo overhead do Insertion Sort supera a vantagem teórica de algoritmos O(n log n) para poucos elementos.
Dados quase ordenados: se o vetor tem poucas inversões (elementos fora de lugar), o desempenho se aproxima de O(n). Ideal para manter dados que recebem atualizações incrementais.
Ordenação online: quando os dados chegam um a um (streaming), o Insertion Sort insere cada novo elemento na posição correta de forma natural.
Caso base de algoritmos híbridos: usado internamente pelo TimSort, Introsort e pela implementação de sort() do Rust.
Estabilidade necessária: quando a ordem relativa de elementos iguais deve ser preservada.

Evite o Insertion Sort quando:

O volume de dados for grande e desordenado — prefira Merge Sort ou Quick Sort.
O desempenho garantido O(n log n) for necessário — considere o Heap Sort.

Comparação com Outros Algoritmos

Característica	Insertion Sort	Bubble Sort	Selection Sort	Merge Sort
Complexidade (média)	O(n²)	O(n²)	O(n²)	O(n log n)
Melhor caso	O(n) ✓	O(n) ✓	O(n²)	O(n log n)
Estável	Sim ✓	Sim ✓	Não	Sim ✓
Adaptativo	Sim ✓	Sim	Não	Não
In-place	Sim ✓	Sim ✓	Sim ✓	Não (O(n))
Uso prático	Caso base	Educacional	Trocas caras	Grandes volumes

O Insertion Sort domina entre os O(n²) por ser o mais eficiente na prática: tem o melhor padrão de acesso à memória (acesso sequencial favorável ao cache), é adaptativo e estável. É por isso que algoritmos profissionais o utilizam como caso base.

Exercícios Práticos

Contagem de inversões: O número de deslocamentos no Insertion Sort é igual ao número de inversões no vetor (pares (i, j) onde i < j mas vetor[i] > vetor[j]). Implemente uma função que conta inversões usando Insertion Sort. Depois, implemente uma versão O(n log n) usando Merge Sort modificado e compare os resultados.
Insertion Sort para listas ligadas: Implemente uma lista ligada simples em Rust e um Insertion Sort para ela. Qual é a vantagem da lista ligada sobre o vetor para o Insertion Sort? Dica: na lista, a inserção é O(1) mas a busca é O(n).
Ordenação parcial: Modifique o Insertion Sort para ordenar apenas os primeiros k menores elementos do vetor. Compare a complexidade com o Selection Sort para a mesma tarefa.
Benchmark: quase ordenado vs. aleatório: Gere vetores de tamanho 10.000 com três níveis de “desordem”: 0 trocas (ordenado), 10 trocas aleatórias e 100 trocas aleatórias. Meça o tempo do Insertion Sort em cada caso usando std::time::Instant. Plote mentalmente a curva de desempenho em função do número de inversões.

Veja Também

Bubble Sort em Rust — algoritmo O(n²) simples com saída antecipada
Selection Sort em Rust — algoritmo O(n²) com mínimo de trocas
Merge Sort em Rust — algoritmo estável O(n log n)
Quick Sort em Rust — algoritmo in-place O(n log n) que usa Insertion Sort como caso base
Vec — Vetores Dinâmicos — a estrutura de dados padrão para ordenação
Slice — Fatias de Memória — métodos sort(), sort_unstable() e rotate_right()
Otimização de Performance em Rust — técnicas para escrever código Rust eficiente