Algoritmos

Bubble sort: o que é e como funciona (com exemplos)

Capa do artigo Bubble sort: o que é e como funciona (com exemplos)
Leitura com foco

Entenda o contexto.
Leve para a prática.

Neste artigo
  1. Por que o nome bubble sort?
  2. Como funciona o bubble sort?
  3. Exemplo de bubble sort passo a passo
  4. Bubble sort em PHP, Python e C
  5. O bubble sort é rápido?
  6. Aí você pergunta: então para que aprender bubble sort?
  7. Agora é com você!

Bubble sort (ordenação por bolha) é um algoritmo de ordenação que percorre o vetor várias vezes, compara dois vizinhos por vez e troca os dois de lugar quando estão fora de ordem. A cada passada, o maior valor que ainda faltava vai parar no fim do vetor.

No artigo sobre busca binária, você viu que ela só funciona com o vetor ordenado. Então hoje vamos aprender a ordenar! Mas antes, a resposta do desafio: para descobrir que o 5 não estava no vetor, a busca binária fez 3 comparações, com o 25, o 7 e o 3. Acertou? Se errou, tudo bem, refaça com calma que você chega lá.

Por que o nome bubble sort?

Bubble é “bolha” em inglês, e sort é “ordenar”. Pense nas bolhas de um copo de refrigerante, que vão subindo até chegar em cima. No bubble sort acontece algo parecido: a cada passada, o maior valor vai “subindo” pelo vetor até chegar na última posição, como uma bolha.

Como funciona o bubble sort?

  • Compare o primeiro valor com o segundo. Se o primeiro for maior, troque os dois de lugar.
  • Faça o mesmo com o segundo e o terceiro, depois com o terceiro e o quarto, até o fim do vetor.
  • Ao terminar a passada, o maior valor está na última posição.
  • Repita, deixando de lado as posições do fim que já estão no lugar, até não sobrar nada para trocar.

É só isso: comparar, trocar e repetir. Simples assim!

Exemplo de bubble sort passo a passo

Vamos ordenar o vetor [5, 3, 8, 1]:

PassadaComparaTroca?Vetor depois
15 e 3Sim[3, 5, 8, 1]
15 e 8Não[3, 5, 8, 1]
18 e 1Sim[3, 5, 1, 8]
23 e 5Não[3, 5, 1, 8]
25 e 1Sim[3, 1, 5, 8]
33 e 1Sim[1, 3, 5, 8]
Passo a passo do bubble sort no vetor [5, 3, 8, 1].
Diagrama da primeira passada do bubble sort no vetor 5, 3, 8, 1, com as comparações e trocas de cada par
A primeira passada do bubble sort: o 8, maior valor, termina na última posição.

Foram 6 comparações para ordenar 4 valores. Observe que na primeira passada o 8 foi para o fim, na segunda foi a vez do 5, e assim o vetor vai ficando ordenado de trás para frente.

Ver a animação do bubble sort, passo a passo
Animação do bubble sort ordenando o vetor 5, 3, 8, 1 em três passadas e seis comparações, com cada par comparado em destaque
O mesmo exemplo em movimento: três passadas, seis comparações, e o vetor fica ordenado de trás para frente.

Bubble sort em PHP, Python e C

Veja em PHP:

<?php

function bubbleSort(array $numeros): array
{
    $tamanho = count($numeros);

    for ($passada = 0; $passada < $tamanho - 1; $passada++) {
        $trocou = false;

        for ($i = 0; $i < $tamanho - 1 - $passada; $i++) {
            if ($numeros[$i] > $numeros[$i + 1]) {
                // troca os dois vizinhos de lugar
                [$numeros[$i], $numeros[$i + 1]] = [$numeros[$i + 1], $numeros[$i]];
                $trocou = true;
            }
        }

        if (!$trocou) {
            break; // nenhuma troca: o vetor já está ordenado
        }
    }

    return $numeros;
}

echo implode(', ', bubbleSort([5, 3, 8, 1])), PHP_EOL; // 1, 3, 5, 8

Em Python:

def bubble_sort(numeros):
    tamanho = len(numeros)

    for passada in range(tamanho - 1):
        trocou = False

        for i in range(tamanho - 1 - passada):
            if numeros[i] > numeros[i + 1]:
                # troca os dois vizinhos de lugar
                numeros[i], numeros[i + 1] = numeros[i + 1], numeros[i]
                trocou = True

        if not trocou:
            break  # nenhuma troca: o vetor já está ordenado

    return numeros


print(bubble_sort([5, 3, 8, 1]))  # [1, 3, 5, 8]

E em C:

#include <stdio.h>

void bubble_sort(int numeros[], int tamanho) {
    for (int passada = 0; passada < tamanho - 1; passada++) {
        int trocou = 0;

        for (int i = 0; i < tamanho - 1 - passada; i++) {
            if (numeros[i] > numeros[i + 1]) {
                // troca os dois vizinhos de lugar
                int temporario = numeros[i];
                numeros[i] = numeros[i + 1];
                numeros[i + 1] = temporario;
                trocou = 1;
            }
        }

        if (!trocou) {
            break; // nenhuma troca: o vetor já está ordenado
        }
    }
}

int main(void) {
    int numeros[] = {5, 3, 8, 1};

    bubble_sort(numeros, 4);

    for (int i = 0; i < 4; i++) {
        printf("%d ", numeros[i]); // 1 3 5 8
    }

    printf("\n");
    return 0;
}

Reparou na variável trocou? Ela é um truque simples: se uma passada inteira termina sem nenhuma troca, o vetor já está ordenado e o algoritmo para ali mesmo, sem perder tempo com passadas inúteis.

O bubble sort é rápido?

Sendo bem sincero: não. Em um vetor com n valores, ele pode fazer até n × (n − 1) ÷ 2 comparações. Veja como esse número cresce:

Tamanho do vetorComparações no pior caso
46
1045
1004.950
1.000499.500
Máximo de comparações do bubble sort conforme o vetor cresce.

O vetor ficou 10 vezes maior e o trabalho ficou perto de 100 vezes maior. É o que chamamos de complexidade O(n²). Se quiser entender essa notação com calma, veja como calcular a complexidade de algoritmos.

Aí você pergunta: então para que aprender bubble sort?

Para aprender a pensar! Ele é o melhor ponto de partida para entender o que um algoritmo de ordenação faz. Quem entende o bubble sort está pronto para entender os mais rápidos.

No trabalho do dia a dia, você usa a ordenação que a própria linguagem já traz. Em PHP:

<?php

$numeros = [5, 3, 8, 1];

sort($numeros);

echo implode(', ', $numeros), PHP_EOL; // 1, 3, 5, 8

E em Python:

numeros = [5, 3, 8, 1]

print(sorted(numeros))  # [1, 3, 5, 8]

Segundo a documentação oficial, a função sort() do PHP usa uma implementação do Quicksort, e o Python usa um algoritmo chamado Timsort. Os dois são bem mais rápidos que o bubble sort em vetores grandes. Só que agora você sabe o que existe por trás de uma linha como sort($numeros), e isso faz toda a diferença!

Agora é com você!

Pegue papel e caneta e ordene o vetor [4, 2, 7, 1, 3] com o bubble sort, passada por passada, e conte quantas trocas acontecem. Depois altere o código, na linguagem que você quiser, para ele contar as trocas e confira o seu resultado.

Não copie e cole: digite, rode, erre e corrija. A capacidade de resolver já está aí com você, o que falta é só treino. A resposta vem no próximo artigo.

O bubble sort é só o primeiro algoritmo de ordenação da nossa jornada: mais adiante você vai conhecer o selection sort e o insertion sort. No próximo artigo começamos uma trilha nova, a das estruturas de dados, com a lista encadeada: um jeito diferente do vetor de guardar valores em sequência. Até lá!

Confiança Sempre!!!

Fontes:

Sobre quem escreve

Walmir Silva

Olá! Sou Walmir, engenheiro de software com MBA em Engenharia de Software e o cérebro por trás do GrowthCode e autor do livro "Além do Código".

Se você acha que programação é apenas sobre escrever código, prepare-se para expandir seus horizontes. Aqui, nós vamos além do código e exploramos as interseções fascinantes entre tecnologia, negócios, artes e filosofia.

Você está em busca de crescimento na carreira? Quer se destacar em um mercado competitivo? Almeja uma vida mais rica em conhecimento e realização? Então você chegou ao lugar certo. No GrowthCode, oferecemos insights profundos, estratégias comprovadas e um toque de sabedoria filosófica para catalisar seu crescimento pessoal e profissional.

Ver todos os artigos →

Continue a conversa

Compartilhe sua perspectiva

O seu endereço de e-mail não será publicado. Campos obrigatórios são marcados com *

Encontre sua próxima resposta

O que você quer aprender?

Preferências de cookies

Os cookies opcionais começam desligados. Você pode mudar a escolha a qualquer momento por esta tela.

NecessáriosSempre ativos

Guardam a sua escolha de cookies e mantêm o site funcionando. Não são usados para publicidade.

Contam visitas e mostram como o site é usado: Google Analytics e Microsoft Clarity, carregados pelo Google Tag Manager. Como esse contêiner também carrega tags de publicidade, as estatísticas só são ativadas junto com Publicidade e marketing.

Exibem anúncios do Google AdSense e medem campanhas e e-mails: pixels da Meta e do TikTok e o Mautic.

Permite que o Google escolha anúncios com base nos seus interesses. Desligado, os anúncios aparecem sem personalização. Depende de Publicidade e marketing.

Também é possível bloquear cookies nas configurações do navegador. Detalhes na Política de privacidade.