Bubble sort

O problema

Uma fila de fichas numeradas está fora de ordem. A única operação permitida é comparar duas fichas vizinhas e trocá-las de lugar.

Repetindo comparações da esquerda para a direita, qual número chega obrigatoriamente ao fim da fila? Quantas vezes é preciso repetir?

Experimente com as fichas 5, 2, 4 e 1 antes de continuar. Acompanhe o 5.

Como funciona

O bubble sort percorre o vetor comparando cada par de vizinhos, v[j] e v[j+1]. Se o da esquerda for maior, troca os dois. Um percurso completo, do início ao fim, é uma passagem. Durante a passagem, o maior valor encontrado é “carregado” pelas trocas, como uma bolha subindo na água, até o fim da parte ainda desorganizada.

Parada antecipada: se uma passagem inteira terminar sem nenhuma troca, todos os vizinhos já estão em ordem, e o vetor está ordenado. Não há por que continuar. É essa regra que torna o bubble sort rápido em listas que já chegam ordenadas.

Inversões: a medida da bagunça

Quanto trabalho o bubble sort vai ter? Depende de quão bagunçado está o vetor, e existe um jeito simples de medir isso. Uma inversão é qualquer par de elementos em que o maior aparece antes do menor, sejam eles vizinhos ou não.

Na prática

Implementação em C

void bubble_sort(int v[], int n) {
    for (int fim = n - 1; fim > 0; fim--) {      // depois de fim, tudo está pronto
        int trocou = 0;
        for (int j = 0; j < fim; j++) {           // compara v[j] com v[j+1]
            if (v[j] > v[j + 1]) {                // > estrito: iguais não trocam
                int temp = v[j];
                v[j] = v[j + 1];
                v[j + 1] = temp;
                trocou = 1;
            }
        }
        if (!trocou) break;                        // passagem sem trocas: acabou
    }
}

Para usar: declare int v[] = {5, 2, 4, 1}; e chame bubble_sort(v, 4);. O resultado é [1, 2, 4, 5], com as 6 comparações e 5 trocas da figura.

Exemplo real: classificação de um concurso

Um concurso publica a classificação por nota, da maior para a menor. O edital diz que, em caso de empate, fica à frente quem se inscreveu primeiro. O vetor já chega em ordem de inscrição. Basta ordenar por nota com o cuidado certo:

#include <stdio.h>

typedef struct {
    char nome[20];
    float nota;
} Candidato;

// Maior nota primeiro. Em empate, quem se inscreveu antes continua na frente.
void classificar(Candidato c[], int n) {
    for (int fim = n - 1; fim > 0; fim--) {
        int trocou = 0;
        for (int j = 0; j < fim; j++) {
            if (c[j].nota < c[j + 1].nota) {      // < estrito: empatados não trocam
                Candidato temp = c[j];            // troca o registro inteiro
                c[j] = c[j + 1];
                c[j + 1] = temp;
                trocou = 1;
            }
        }
        if (!trocou) break;
    }
}

int main(void) {
    Candidato c[] = {                   // em ordem de inscrição
        {"Ana", 8.5f}, {"Bia", 7.0f}, {"Caio", 8.5f}, {"Davi", 9.0f}
    };
    int n = sizeof c / sizeof c[0];
    classificar(c, n);
    for (int i = 0; i < n; i++) {
        printf("%d. %s (%.1f)\n", i + 1, c[i].nome, c[i].nota);
    }
    return 0;
}

Ana e Caio empataram com 8.5. Ana se inscreveu antes e ficou à frente, como manda o edital. Isso só acontece por causa de um detalhe: o sinal < estrito.

Estabilidade: por que um sinal muda tudo

Um algoritmo de ordenação é estável quando elementos empatados mantêm entre si a ordem em que chegaram. O bubble sort é estável porque só troca vizinhos quando estão estritamente fora de ordem. Dois empatados nunca trocam, então nunca se ultrapassam. Basta trocar < por <= para perder essa garantia:

Estabilidade importa sempre que a ordem de chegada carrega informação: inscrição, horário do pedido, posição em uma lista anterior. Também permite ordenar por vários critérios em etapas: ordene primeiro por nome e depois, de forma estável, por nota. O resultado fica por nota e, nos empates, por nome.

Quanto custa na prática?

Medimos o bubble sort desta aula com três tipos de entrada:

Os números da coluna decrescente seguem exatamente a fórmula n(n−1)/2: 1 000 × 999 / 2 = 499 500, e 50 000 × 49 999 / 2 ≈ 1,25 bilhão.

Três lições saem dessa tabela:

1. Lista já ordenada: uma passagem e pronto. Graças à parada antecipada, 50 mil elementos ordenados custam só 49 999 comparações.
2. Lista bagunçada: o custo cresce com o quadrado. Com 5 vezes mais elementos (10 mil para 50 mil), o tempo aumentou cerca de 26 vezes, perto dos 25 que o quadrado prevê. Com 1 milhão de elementos, a estimativa é de uns 20 minutos. No pior caso, são n(n−1)/2 comparações: cada elemento é comparado com praticamente todos os outros.
3. Contar operações não conta tudo. O vetor aleatório fez menos trocas que o decrescente e mesmo assim foi mais lento. O número de operações não conta toda a história do tempo.

Comparação com as outras ordenações da revisão

Na prática, o bubble sort raramente é a melhor escolha: o insertion sort, da próxima aula, faz o mesmo serviço movendo menos dados. O valor do bubble sort está no que ele ensina: invariantes, inversões e estabilidade.

Exercícios progressivos

Use as figuras da aula como modelo: desenhe o vetor e marque o par comparado em cada etapa. A dica não entrega a resposta: ela indica a pergunta certa a fazer.

#include <string.h>

void ordenar_letras(char s[]) {
    int n = (int)strlen(s);
    for (int fim = n - 1; fim > 0; fim--) {
        int trocou = 0;
        for (int j = 0; j < fim; j++) {
            if (s[j] > s[j + 1]) {             // compara os códigos das letras
                char temp = s[j];
                s[j] = s[j + 1];
                s[j + 1] = temp;
                trocou = 1;
            }
        }
        if (!trocou) break;
    }
}

int anagramas(const char *a, const char *b) {
    char x[50], y[50];
    if (strlen(a) != strlen(b) || strlen(a) >= sizeof x) return 0;
    strcpy(x, a);                  // copia: as originais não podem ser alteradas
    strcpy(y, b);
    ordenar_letras(x);             // "amor" -> "amor", "roma" -> "amor"
    ordenar_letras(y);
    return strcmp(x, y) == 0;
}