Ordenação por bolha

A ordenação por bolha é um algoritmo de ordenação baseado em comparações que compara repetidamente elementos adjacentes e os troca quando estão fora de ordem crescente. Ao fim de cada passagem completa, o maior valor ainda não ordenado chega à sua posição definitiva, à direita. O nome descreve esse movimento repetido pela lista. A ordenação por bolha é fácil de acompanhar e implementar, mas seu tempo de execução quadrático a torna uma escolha inadequada para coleções grandes.

Algoritmo de ordenação por bolha

Para um vetor A com n elementos, compare A[0] com A[1], depois A[1] com A[2] e continue pelo trecho ainda não ordenado. Sempre que o valor à esquerda for maior que o valor à direita, troque-os. Essa condição produz ordem crescente; inverta a comparação para ordenar em ordem decrescente.

Uma passagem percorre o vetor da esquerda para a direita. Ao final, o maior valor do trecho percorrido estará no limite à direita, então a próxima passagem pode terminar uma posição antes. A primeira passagem percorre n - 1 pares, a seguinte percorre n - 2 e assim por diante. Uma implementação com número fixo de passagens executa n - 1 passagens, embora a última tenha apenas um par para verificar. Listas com menos de dois elementos não precisam de comparações.

Exemplo do algoritmo de ordenação por bolha

Considere a entrada (5, 3, 4, 2, 1). Na primeira passagem, compare os pares adjacentes em sequência: 5 e 3 são trocados, resultando em (3, 5, 4, 2, 1); 5 e 4 são trocados, resultando em (3, 4, 5, 2, 1); 5 e 2 são trocados, resultando em (3, 4, 2, 5, 1); em seguida, 5 e 1 são trocados, resultando em (3, 4, 2, 1, 5). O maior valor agora está fixo à direita.

A segunda passagem percorre apenas os quatro primeiros valores e produz (3, 2, 1, 4, 5). A terceira passagem transforma esse prefixo não ordenado em (2, 1, 3, 4, 5), e a quarta o transforma em (1, 2, 3, 4, 5). Esse percurso mostra por que o limite diminui após cada passagem e por que os valores já fixados não são comparados novamente.

Implementação da ordenação por bolha em C++

Este programa completo ordena o exemplo no próprio vetor. O limite do laço interno n - i - 1 evita comparar o sufixo já fixado, enquanto values[j] > values[j + 1] troca um par adjacente fora de ordem e faz os valores menores avançarem para a esquerda.

Execute este exemplo:

O código e os rótulos ou saídas exibidos nesta seção permanecem em inglês.

#include <iostream>
#include <utility>
#include <vector>

void bubble_sort(std::vector<int>& values) {
    const int n = static_cast<int>(values.size());
    for (int i = 0; i < n - 1; ++i) {
        for (int j = 0; j < n - i - 1; ++j) {
            if (values[j] > values[j + 1]) {
                std::swap(values[j], values[j + 1]);
            }
        }
    }
}

int main() {
    std::vector<int> values{5, 3, 4, 2, 1};
    bubble_sort(values);
    std::cout << "Sorted:";
    for (int value : values) {
        std::cout << ' ' << value;
    }
    std::cout << '\n';
}

Sorted: 1 2 3 4 5

A execução fornecida foi concluída com sucesso e imprimiu os valores ordenados após o rótulo Sorted:, que permanece em inglês no exemplo. A saída foi Sorted: 1 2 3 4 5.

Complexidade e limitações da ordenação por bolha

A implementação com número fixo de passagens realiza (n - 1) + (n - 2) + ... + 1, ou n(n - 1) / 2, comparações, qualquer que seja a ordem inicial dos valores. Portanto, as complexidades de tempo no melhor, no caso médio e no pior caso são todas O(n²). O pior caso, como uma entrada em ordem inversa, também exige muitas trocas. A implementação modifica o vetor diretamente e usa apenas um valor temporário para cada troca, então sua complexidade de espaço auxiliar é O(1).

Uma variante com saída antecipada pode verificar se houve alguma troca durante a passagem e parar quando uma passagem não modificar a lista. Essa versão leva O(n) tempo quando a entrada já está ordenada, enquanto os casos médio e pior continuam em O(n²). O código com número fixo de passagens acima não inclui essa otimização. A ordenação por bolha é útil para aprender comparações entre elementos adjacentes e para entradas muito pequenas, mas, em geral, os algoritmos de ordenação da biblioteca padrão são mais adequados para coleções maiores.