---
title: "Bubble Sort em Rust"
url: "https://rustlang.com.br/algoritmos/bubble-sort/"
markdown_url: "https://rustlang.com.br/algoritmos/bubble-sort.MD"
description: "Aprenda Bubble Sort em Rust com diagramas visuais, análise Big-O, código completo e otimizações. Guia completo em português."
date: "2026-02-24"
author: "Equipe Rust Brasil"
---

# Bubble Sort em Rust

Aprenda Bubble Sort em Rust com diagramas visuais, análise Big-O, código completo e otimizações. Guia completo em português.


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]`:

```text
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

```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

```text
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:

```rust
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.

```rust
/// 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").

```rust
/// 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:

```rust
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](/algoritmos/quick-sort/) ou [Merge Sort](/algoritmos/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](/algoritmos/selection-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 | 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

1. **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.

2. **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?

3. **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 }`.

4. **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](/algoritmos/selection-sort/) — outro algoritmo O(n²) com menos trocas
- [Insertion Sort em Rust](/algoritmos/insertion-sort/) — alternativa O(n²) mais eficiente na prática
- [Merge Sort em Rust](/algoritmos/merge-sort/) — algoritmo O(n log n) estável
- [Quick Sort em Rust](/algoritmos/quick-sort/) — algoritmo O(n log n) in-place
- [Vec — Vetores Dinâmicos](/stdlib/vec/) — a estrutura de dados mais usada em ordenação
- [Slice — Fatias de Memória](/stdlib/slice/) — operações sobre fatias, incluindo `sort()` e `sort_unstable()`
- [Eq e Ord — Comparação e Ordenação](/stdlib/eq-ord/) — traits de comparação usados pelos algoritmos de ordenação