Bubble Sort em Rust | Rust Brasil

O Bubble Sort (ordenação por bolha) é um dos algoritmos de ordenação mais simples e intuitivos que existem. Seu nome vem da analogia com bolhas de ar que sobem em um líquido: a cada passagem pelo vetor, o maior elemento “flutua” até sua posição correta no final. Embora não seja eficiente para grandes volumes de dados, o Bubble Sort é um excelente ponto de partida para estudar algoritmos de ordenação, pois sua lógica é direta e fácil de visualizar.

Na prática, o Bubble Sort é utilizado em contextos educacionais e em situações onde o conjunto de dados é muito pequeno ou já está quase ordenado. Sua principal vantagem é a simplicidade de implementação e o fato de ser um algoritmo estável — elementos iguais mantêm sua ordem relativa original.

Como Funciona

O Bubble Sort percorre o vetor repetidamente, comparando pares de elementos adjacentes. Se o elemento da esquerda for maior que o da direita, eles são trocados. Esse processo se repete até que nenhuma troca seja necessária, indicando que o vetor está ordenado.

Vamos visualizar o funcionamento com o vetor [5, 3, 8, 1, 2]:

Vetor inicial: [5, 3, 8, 1, 2]

=== Passagem 1 ===
[5, 3, 8, 1, 2]   compara 5 e 3 → troca
 ^  ^
[3, 5, 8, 1, 2]   compara 5 e 8 → ok
    ^  ^
[3, 5, 8, 1, 2]   compara 8 e 1 → troca
       ^  ^
[3, 5, 1, 8, 2]   compara 8 e 2 → troca
          ^  ^
[3, 5, 1, 2, 8]   ✓ 8 está na posição final

=== Passagem 2 ===
[3, 5, 1, 2, 8]   compara 3 e 5 → ok
 ^  ^
[3, 5, 1, 2, 8]   compara 5 e 1 → troca
    ^  ^
[3, 1, 5, 2, 8]   compara 5 e 2 → troca
       ^  ^
[3, 1, 2, 5, 8]   ✓ 5 está na posição final

=== Passagem 3 ===
[3, 1, 2, 5, 8]   compara 3 e 1 → troca
 ^  ^
[1, 3, 2, 5, 8]   compara 3 e 2 → troca
    ^  ^
[1, 2, 3, 5, 8]   ✓ 3 está na posição final

=== Passagem 4 ===
[1, 2, 3, 5, 8]   compara 1 e 2 → ok
 ^  ^
[1, 2, 3, 5, 8]   Nenhuma troca! → vetor ordenado ✓

Resultado: [1, 2, 3, 5, 8]

Observe como a cada passagem o maior elemento não ordenado “borbulha” até sua posição correta. A otimização de saída antecipada (early exit) detecta quando nenhuma troca ocorre em uma passagem completa, encerrando o algoritmo antes de completar todas as iterações.

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): ocorre quando o vetor já está ordenado. Com a otimização de saída antecipada, o algoritmo faz apenas uma passagem sem trocas e encerra.
Caso médio O(n²): para vetores com elementos em ordem aleatória, o número de comparações e trocas cresce quadraticamente.
Pior caso O(n²): ocorre quando o vetor está em ordem decrescente. Cada elemento precisa percorrer todo o caminho até sua posição final.
Espaço O(1): o Bubble Sort é um algoritmo in-place, utilizando apenas uma variável temporária para as trocas.

Implementação em Rust

/// Bubble Sort genérico com otimização de saída antecipada.
/// Ordena o slice in-place em ordem crescente.
/// Requer que os elementos implementem `PartialOrd`.
fn bubble_sort<T: PartialOrd>(vetor: &mut [T]) {
    let n = vetor.len();
    if n <= 1 {
        return;
    }

    for i in 0..n {
        let mut houve_troca = false;

        // A cada passagem, o maior elemento vai para o final.
        // Portanto, podemos ignorar os últimos `i` elementos.
        for j in 0..n - 1 - i {
            if vetor[j] > vetor[j + 1] {
                vetor.swap(j, j + 1);
                houve_troca = true;
            }
        }

        // Se nenhuma troca ocorreu, o vetor já está ordenado.
        if !houve_troca {
            break;
        }
    }
}

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

    // Exemplo com strings
    let mut palavras = vec!["rust", "algoritmo", "bolha", "dados"];
    println!("\nAntes:  {:?}", palavras);
    bubble_sort(&mut palavras);
    println!("Depois: {:?}", palavras);

    // Exemplo com floats
    let mut valores = vec![3.14, 1.41, 2.72, 0.58];
    println!("\nAntes:  {:?}", valores);
    bubble_sort(&mut valores);
    println!("Depois: {:?}", valores);
}

Exemplo de Execução

Antes:  [5, 3, 8, 1, 2]
Depois: [1, 2, 3, 5, 8]

Antes:  ["rust", "algoritmo", "bolha", "dados"]
Depois: ["algoritmo", "bolha", "dados", "rust"]

Antes:  [3.14, 1.41, 2.72, 0.58]
Depois: [0.58, 1.41, 2.72, 3.14]

Para entender melhor a execução interna, veja esta versão com rastreamento detalhado:

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

    for i in 0..n {
        let mut houve_troca = false;
        passagem += 1;
        println!("--- Passagem {} ---", passagem);

        for j in 0..n - 1 - i {
            print!("  Comparando {} e {} ", vetor[j], vetor[j + 1]);
            if vetor[j] > vetor[j + 1] {
                vetor.swap(j, j + 1);
                println!("→ troca! → {:?}", vetor);
                houve_troca = true;
            } else {
                println!("→ ok");
            }
        }

        if !houve_troca {
            println!("  Nenhuma troca → vetor ordenado!");
            break;
        }
    }
}

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

Variações e Otimizações

1. Bubble Sort com Limite de Troca

Em vez de apenas reduzir o limite superior em 1 a cada passagem, registramos a posição da última troca. Todos os elementos após essa posição já estão ordenados.

/// Bubble Sort otimizado que rastreia a posição da última troca.
fn bubble_sort_otimizado<T: PartialOrd>(vetor: &mut [T]) {
    let mut n = vetor.len();
    if n <= 1 {
        return;
    }

    loop {
        let mut ultima_troca = 0;

        for i in 0..n - 1 {
            if vetor[i] > vetor[i + 1] {
                vetor.swap(i, i + 1);
                ultima_troca = i + 1;
            }
        }

        // Se não houve troca, ultima_troca permanece 0
        if ultima_troca == 0 {
            break;
        }
        // Na próxima passagem, só precisamos ir até a última troca
        n = ultima_troca;
    }
}

fn main() {
    let mut dados = vec![1, 2, 5, 3, 4, 6, 7, 8];
    println!("Antes:  {:?}", dados);
    bubble_sort_otimizado(&mut dados);
    println!("Depois: {:?}", dados);
    // Apenas os elementos 5, 3, 4 precisam ser reorganizados
}

2. Cocktail Shaker Sort (Bubble Sort Bidirecional)

Percorre o vetor nos dois sentidos alternadamente, reduzindo o problema de elementos pequenos no final do vetor (o problema da “tartaruga”).

/// Cocktail Shaker Sort — variante bidirecional do Bubble Sort.
fn cocktail_sort<T: PartialOrd>(vetor: &mut [T]) {
    let n = vetor.len();
    if n <= 1 {
        return;
    }

    let mut inicio = 0;
    let mut fim = n - 1;
    let mut houve_troca = true;

    while houve_troca {
        houve_troca = false;

        // Passagem da esquerda para a direita
        for i in inicio..fim {
            if vetor[i] > vetor[i + 1] {
                vetor.swap(i, i + 1);
                houve_troca = true;
            }
        }
        fim -= 1;

        if !houve_troca {
            break;
        }
        houve_troca = false;

        // Passagem da direita para a esquerda
        for i in (inicio..=fim).rev() {
            if vetor[i] > vetor[i + 1] {
                vetor.swap(i, i + 1);
                houve_troca = true;
            }
        }
        inicio += 1;
    }
}

fn main() {
    let mut v = vec![2, 3, 4, 5, 1]; // 1 é a "tartaruga"
    println!("Antes:  {:?}", v);
    cocktail_sort(&mut v);
    println!("Depois: {:?}", v);
}

3. Ordenação Decrescente

Basta inverter a comparação para ordenar do maior para o menor:

fn bubble_sort_decrescente<T: PartialOrd>(vetor: &mut [T]) {
    let n = vetor.len();
    for i in 0..n {
        let mut houve_troca = false;
        for j in 0..n - 1 - i {
            if vetor[j] < vetor[j + 1] {  // < em vez de >
                vetor.swap(j, j + 1);
                houve_troca = true;
            }
        }
        if !houve_troca {
            break;
        }
    }
}

fn main() {
    let mut v = vec![5, 3, 8, 1, 2];
    bubble_sort_decrescente(&mut v);
    println!("Decrescente: {:?}", v); // [8, 5, 3, 2, 1]
}

Quando Usar

O Bubble Sort é a escolha adequada nos seguintes cenários:

Fins educacionais: é o algoritmo ideal para introduzir conceitos de ordenação, trocas e complexidade algorítmica.
Vetores muito pequenos (n < 20): o overhead de algoritmos mais sofisticados pode não compensar para poucos elementos.
Vetores quase ordenados: com a otimização de saída antecipada, o Bubble Sort se aproxima de O(n) quando poucos elementos estão fora de lugar.
Detecção de ordenação: uma passagem sem trocas confirma que os dados estão ordenados — útil como verificação rápida.
Memória extremamente limitada: por ser in-place com O(1) de espaço extra, funciona onde outros algoritmos não cabem.

Evite o Bubble Sort quando:

O volume de dados for grande (n > 100).
A performance for crítica — prefira Quick Sort ou Merge Sort.
Existir necessidade de ordenação frequente de conjuntos mutáveis — considere estruturas como BinaryHeap.

Comparação com Outros Algoritmos

Característica	Bubble Sort	Selection Sort	Insertion Sort
Complexidade (média)	O(n²)	O(n²)	O(n²)
Melhor caso	O(n) ✓	O(n²)	O(n) ✓
Estável	Sim ✓	Não	Sim ✓
Adaptativo	Sim ✓	Não	Sim ✓
Trocas (média)	O(n²)	O(n) ✓	O(n²)
In-place	Sim	Sim	Sim
Uso prático	Educacional	Educacional	Pequenos vetores

O Insertion Sort é geralmente preferido ao Bubble Sort na prática, pois faz menos comparações em vetores parcialmente ordenados e tem um desempenho real melhor devido ao padrão de acesso à memória mais favorável ao cache.

Exercícios Práticos

Contagem de trocas: Modifique o Bubble Sort para retornar o número total de trocas realizadas. Use isso para medir o “grau de desordem” de um vetor. Dica: o número de trocas no Bubble Sort é igual ao número de inversões no vetor.
Ordenação parcial: Implemente uma função que use Bubble Sort para encontrar apenas os k maiores elementos de um vetor (executando apenas k passagens). Qual é a complexidade dessa versão?
Ordenação por critério personalizado: Modifique a implementação genérica para aceitar um parâmetro de função de comparação (Fn(&T, &T) -> std::cmp::Ordering), permitindo ordenar por qualquer critério. Teste com uma struct Aluno { nome: String, nota: f64 }.
Benchmark comparativo: Implemente o Bubble Sort e o Insertion Sort. Gere vetores aleatórios de tamanhos 100, 1.000 e 10.000. Meça o tempo de execução de cada um usando std::time::Instant e compare os resultados. Quem vence? Por quê?

Veja Também

Selection Sort em Rust — outro algoritmo O(n²) com menos trocas
Insertion Sort em Rust — alternativa O(n²) mais eficiente na prática
Merge Sort em Rust — algoritmo O(n log n) estável
Quick Sort em Rust — algoritmo O(n log n) in-place
Vec — Vetores Dinâmicos — a estrutura de dados mais usada em ordenação
Slice — Fatias de Memória — operações sobre fatias, incluindo sort() e sort_unstable()
Eq e Ord — Comparação e Ordenação — traits de comparação usados pelos algoritmos de ordenação