Algoritmos de Ordenação — Bubble Sort, Merge Sort e Quick Sort Comparados

Um algoritmo de ordenação reorganiza os mesmos itens em uma certa ordem, como do menor para o maior. Se você quer a resposta curta primeiro, o bubble sort é simples, mas geralmente lento demais para listas grandes; o merge sort oferece desempenho confiável de $O(n \log n)$; e o quick sort costuma ser rápido na prática quando suas partições ficam razoavelmente equilibradas.

A pergunta certa não é "qual ordenação é melhor?", mas "melhor em que condição?". O bubble sort ensina trocas locais, o merge sort mostra claramente a estratégia de dividir para conquistar, e o quick sort mostra por que a velocidade no caso médio pode ser forte mesmo sem garantia no pior caso.

O Que Fazem os Algoritmos de Ordenação

Dada uma lista como $[5, 1, 4, 2]$, o algoritmo deve retornar os mesmos valores em ordem:

$$[1, 2, 4, 5]$$

Isso parece simples, mas algoritmos diferentes chegam a esse resultado de maneiras bem diferentes. As principais diferenças são:

• como eles movem os itens
• quantas comparações ou trocas eles tendem a usar
• quanta memória extra eles precisam
• o quanto são sensíveis a padrões ruins de entrada

Bubble Sort: Trocas Repetidas Entre Vizinhos

O bubble sort percorre a lista e troca itens adjacentes que estão fora de ordem. Depois de uma passagem completa, o maior item ainda não ordenado "borbulhou" até o final.

Em $[5, 1, 4, 2]$, a primeira passagem fica assim:

$$[5, 1, 4, 2] \to [1, 5, 4, 2] \to [1, 4, 5, 2] \to [1, 4, 2, 5]$$

Depois, ele repete o processo na parte restante não ordenada até que nenhuma troca seja necessária.

O bubble sort é útil principalmente para aprendizado. Em geral, ele tem complexidade de tempo $O(n^2)$, então o número de comparações cresce rapidamente à medida que a lista aumenta. Para exemplos pequenos em sala de aula, isso é aceitável. Para tarefas reais de ordenação, normalmente não é a escolha certa.

Merge Sort: Dividir, Ordenar e Depois Mesclar

O merge sort usa a ideia de dividir para conquistar. Ele divide a lista em partes menores, ordena essas partes e depois mescla os pedaços ordenados de volta.

Para $[5, 1, 4, 2]$, uma forma clara de ver é:

$$[5, 1, 4, 2] \to [5, 1] + [4, 2]$$

Ordene cada metade:

$$[5, 1] \to [1, 5], \qquad [4, 2] \to [2, 4]$$

Depois mescle as duas metades ordenadas:

$$[1, 5] + [2, 4] \to [1, 2, 4, 5]$$

A principal força do merge sort é a previsibilidade. Seu tempo de execução é $O(n \log n)$ na análise usual, não apenas em média. O principal custo é a memória: implementações comuns baseadas em arrays usam espaço extra durante a mesclagem.

Quick Sort: Particionar em Torno de um Pivô

O quick sort também usa dividir para conquistar, mas de um jeito diferente. Ele escolhe um pivô, coloca os itens menores de um lado e os maiores do outro, e então ordena os dois lados recursivamente.

Usando o pivô $4$ em $[5, 1, 4, 2]$, uma partição possível é:

$$[1, 2] \;|\; 4 \;|\; [5]$$

Agora as partes da esquerda e da direita são bem menores, então a ordenação termina rapidamente.

O quick sort costuma ser rápido na prática porque muitas implementações fazem a partição no próprio array e reduzem o problema rapidamente quando o pivô divide a lista de forma razoavelmente boa. Mas essa condição importa. Se as escolhas de pivô forem repetidamente ruins, como produzir um lado minúsculo e outro quase completo várias vezes, o pior caso passa a ser $O(n^2)$.

Bubble Sort vs Merge Sort vs Quick Sort

Algoritmo	Ideia central	Tempo típico	Tempo no pior caso	Memória extra
Bubble sort	Trocas repetidas entre adjacentes	$O(n^2)$	$O(n^2)$	Baixa
Merge sort	Divide, ordena as metades e mescla	$O(n \log n)$	$O(n \log n)$	Maior em implementações comuns com arrays
Quick sort	Particiona em torno de um pivô	Frequentemente $O(n \log n)$	$O(n^2)$	Frequentemente menor que no merge sort

Se você quiser guardar uma conclusão prática, é esta: bubble sort é um algoritmo didático, merge sort é a opção estável e previsível, e quick sort costuma ser a escolha prática em velocidade quando a implementação lida bem com os pivôs.

Um Exemplo Resolvido na Mesma Lista

Use a mesma lista:

$$[5, 1, 4, 2]$$

O bubble sort continua corrigindo erros locais. Ele não "enxerga" a estrutura inteira, então pode precisar de muitas passagens.

O merge sort primeiro quebra o problema em pedaços menores já ordenados e depois os combina. Essa estrutura é o motivo de seu desempenho continuar confiável à medida que a lista cresce.

O quick sort tenta fazer uma divisão forte logo no começo. Se a divisão for equilibrada o suficiente, o restante do trabalho diminui rapidamente.

É por isso que os estudantes costumam lembrar melhor dos números de complexidade depois de ver uma lista passar por cada método. Os números não são rótulos arbitrários. Eles refletem como o algoritmo reduz a desordem.

Erros Comuns ao Comparar Algoritmos de Ordenação

Supor Que o Quick Sort É Sempre Mais Rápido

O quick sort costuma ser rápido na prática, mas não é garantidamente o mais rápido em todos os casos. Um comportamento ruim na escolha do pivô pode prejudicá-lo bastante.

Tratar Algoritmos $O(n \log n)$ Como Se Fossem Iguais

Merge sort e quick sort podem ter a mesma taxa média de crescimento sem se comportarem da mesma forma no uso de memória, nas garantias de pior caso ou nos detalhes de implementação.

Usar Bubble Sort Porque É Fácil de Programar

Facilidade de implementação não é o mesmo que adequação. Para demonstrações pequenas, o bubble sort serve bem. Para entradas reais maiores, ele normalmente faz trabalho desnecessário.

Esquecer o Modelo de Entrada

Essas comparações normalmente assumem ordenação por comparação em entradas gerais. Se os dados tiverem uma estrutura especial, ordenações sem comparação, como counting sort, podem mudar completamente a decisão.

Quando Cada Algoritmo de Ordenação É Usado

O bubble sort é usado principalmente para ensino, rastreamento passo a passo e exemplos muito pequenos em que a clareza importa mais do que o desempenho.

O merge sort é usado quando um comportamento consistente de $O(n \log n)$ importa e memória extra é aceitável. Ele também se encaixa naturalmente em listas ligadas e em situações em que a estabilidade da ordenação importa, dependendo da implementação.

O quick sort é usado quando a velocidade prática é importante e a implementação tem uma boa estratégia de pivô ou proteções de fallback. Muitas estratégias de ordenação de bibliotecas padrão usam ideias do quick sort junto com salvaguardas, em vez de uma versão ingênua de livro-texto.

Uma Forma Rápida de Lembrar a Diferença

Lembre deles pelo movimento:

• bubble sort corrige vizinhos
• merge sort constrói metades ordenadas
• quick sort divide em torno de um pivô

Essa imagem mental é mais útil do que decorar três nomes e três fórmulas.

Tente Sua Própria Versão

Pegue a lista $[7, 3, 6, 1]$ e acompanhe uma passagem do bubble sort, um ciclo de divisão e mesclagem do merge sort e uma partição por pivô do quick sort. Se você consegue explicar por que a lista muda de forma diferente em cada caso, então o conceito fez sentido.