Ordenação da bolha: trocar vizinhos

Comparar vizinhos e trocar

A ordenação da bolha nasce de uma ideia que uma criança entenderia: se dois vizinhos estão na ordem errada, troque-os de lugar. Você percorre a lista da esquerda para a direita, olhando pares de itens grudados. Se o da esquerda é maior que o da direita, eles estão fora de ordem, então você os troca. Se já estão na ordem certa, deixa como está e segue para o próximo par. Ao terminar uma passada completa pela lista, acontece algo bonito: o maior valor de todos, empurrado troca após troca, chegou ao fim da lista, como uma bolha de ar que sobe até o topo da água. Por isso o método se chama bolha. O maior já está no lugar; falta ordenar o resto.

Uma passada só não basta, porque ela garante apenas que o maior chegou ao fim. Os outros valores podem ainda estar desarrumados. Então você repete: faz outra passada, e o segundo maior sobe até a penúltima posição; outra, e o terceiro maior se acomoda; e assim por diante. Cada passada acerta mais um item nas posições do fim, então a parte já ordenada cresce de trás para frente. Você para quando uma passada inteira não precisa de nenhuma troca, sinal de que todos os vizinhos já estão em ordem e, portanto, a lista inteira está ordenada. Esse é o momento em que a bolha declara vitória.

A troca de dois valores, com cuidado

A operação no coração da bolha é a troca de dois valores, e ela esconde uma pegadinha clássica. Trocar o conteúdo de duas caixas parece simples: ponha o valor da caixa A na B e o da B na A. Mas se você faz direto, na primeira linha o valor de A sobrescreve o de B, e o valor original de B se perde para sempre; a segunda linha acaba copiando A para A. O resultado é as duas caixas com o mesmo valor, não trocadas. A solução é usar uma terceira caixa, um auxiliar, para guardar um dos valores antes de sobrescrever: guarde A no auxiliar, copie B para A, e então copie o auxiliar para B. É como trocar o conteúdo de dois copos cheios: você precisa de um terceiro copo vazio para não derramar.

// troca correta de duas posições usando um auxiliar:
auxiliar <- lista[i]
lista[i] <- lista[j]
lista[j] <- auxiliar

// a bolha, em pseudocódigo:
repita
  trocou <- falso
  para i de 0 até tamanho - 2 faça
    se lista[i] > lista[i + 1] então
      auxiliar <- lista[i]
      lista[i] <- lista[i + 1]
      lista[i + 1] <- auxiliar
      trocou <- verdadeiro
    fim
  fim
até trocou = falso   // parou quando uma passada não trocou nada

A troca usa um auxiliar para não perder um valor. A bolha repete passadas até uma delas não trocar nada.

lista <- [3, 1, 4, 2]
// uma passada: compara (3,1)->troca, (3,4)->fica, (4,2)->troca

Simples de entender, lenta de rodar

A ordenação da bolha é campeã de clareza, mas não de velocidade. Repare que ela usa dois laços aninhados: um para as passadas e outro para percorrer os pares dentro de cada passada. Você já sabe do módulo de laços aninhados o que isso significa: o custo cresce com o quadrado do tamanho. Para dez itens, são cerca de cem comparações; para mil, cerca de um milhão; para um milhão de itens, um trilhão, o que é inviável. Por isso a bolha é ótima para aprender e para listas pequenas, mas ninguém a usa para ordenar dados grandes de verdade. As linguagens reais trazem algoritmos bem mais espertos, que ordenam um milhão de itens num piscar de olhos usando ideias como dividir para conquistar. A bolha ensina o raciocínio; a eficiência dela é o gancho perfeito para o próximo módulo.