Bubble sort
O bubble sort (ordenação por bolha) é o algoritmo de ordenação mais simples de descrever: comparar dois vizinhos, trocá-los se estiverem na ordem errada, e repetir. É lento em listas longas, mas cada passo é fácil de seguir, o que faz dele o clássico primeiro algoritmo para observar.
A ideia
Percorra a lista da esquerda para a direita e observe cada par de vizinhos. Se o valor da esquerda for maior do que o da direita, troque-os. Ao chegar ao fim, o maior valor foi levado até à última posição, tal como uma bolha sobe à superfície. Esse percurso chama-se passagem. Repita as passagens até a lista estar ordenada.
Um exemplo
Considere 5, 1, 4, 2, 8. A primeira passagem compara 5 e 1 e troca-os, depois 5 e 4 (troca), 5 e 2 (troca) e 5 e 8 (sem troca): 1, 4, 2, 5, 8. O 8 está agora na posição final. A segunda passagem compara 1 e 4 (sem troca), 4 e 2 (troca) e 4 e 5 (sem troca): 1, 2, 4, 5, 8. A terceira passagem não faz nenhuma troca, por isso a lista está ordenada: 9 comparações e 4 trocas.
Porque cada passagem deixa mais um valor no lugar
Durante uma passagem, o maior valor visto até então é sempre levado em frente: quando a passagem o alcança, cada comparação move-o mais uma posição para a direita. Assim, a primeira passagem põe o maior valor em último, a segunda põe o segundo maior logo antes dele, e assim por diante. Após a passagem k, as últimas k posições são definitivas, e a passagem seguinte pode parar uma posição antes. É por isso que as passagens ficam mais curtas.
As trocas igualam as inversões
Uma inversão é um par de valores na ordem errada: um valor maior algures antes de um menor. Trocar dois vizinhos fora de ordem remove exatamente uma inversão e não cria nenhuma. Assim, o bubble sort faz exatamente tantas trocas quantas as inversões da lista inicial, seja qual for a ordem das comparações. Uma lista ordenada não tem nenhuma; uma lista invertida de n valores tem n(n − 1)/2, o máximo possível.
A paragem antecipada e o custo
Se uma passagem inteira não fizer trocas, todos os vizinhos estão por ordem e a lista está ordenada. Verificar isso permite ao bubble sort terminar uma lista ordenada numa só passagem de n − 1 comparações. No pior caso, continua a precisar de n − 1 passagens e n(n − 1)/2 comparações, e em média o número de trocas é n(n − 1)/4. Ambos crescem com n², por isso duplicar a lista torna a ordenação cerca de quatro vezes mais longa.
O bubble sort é estável: valores iguais nunca trocam, por isso mantêm a ordem. Ordena no próprio lugar, sem memória extra. O insertion sort partilha estas propriedades e costuma precisar de menos passos, e o merge sort e o quicksort demoram um tempo proporcional a n log n, o que é muito menos em listas longas.
Explore
Abra a aplicação e prima Reproduzir, ou prima Avançar para ir uma comparação de cada vez. Os dois valores comparados ficam destacados, uma troca aparece com cor própria e os valores já no lugar ficam verdes. Experimente uma lista invertida para ver o pior caso, uma quase ordenada para ver a paragem antecipada terminar a ordenação após poucas passagens, ou escreva os números do exemplo acima.
Perguntas frequentes
Qual é a complexidade temporal do bubble sort?
O(n²) no pior caso e no caso médio: até n(n − 1)/2 comparações para n valores. Com a paragem antecipada, uma lista já ordenada demora O(n), uma só passagem. Precisa apenas de O(1) de memória extra.
O bubble sort é estável?
Sim. Só troca dois vizinhos quando o da esquerda é estritamente maior, por isso valores iguais nunca se ultrapassam e mantêm a ordem original.
Qual é a diferença entre bubble sort e insertion sort?
Ambos trocam vizinhos e ambos fazem tantas trocas quantas as inversões. O bubble sort faz passagens completas pela parte por ordenar; o insertion sort recua cada novo valor só até onde precisa, por isso costuma fazer menos comparações, sobretudo em listas quase ordenadas.
Quando é o bubble sort uma boa escolha?
Sobretudo para ensinar, e para listas muito curtas em que a simplicidade conta mais do que a velocidade. Para tudo o resto, a ordenação incluída na linguagem de programação é muito mais rápida.
Pronto para experimentar?
Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.
Experimentar o bubble sort