Bubble Sort

Algoritmo de Ordenação da Bolha (Bubble Sort)

O algoritmo Bubble Sort utiliza a técnica chamada de ordenação por submersão (sinking sort) e funciona da seguinte forma: os valores maiores submergem para o final da lista. Ao mesmo tempo, os valores menores sobem gradualmente até o topo do lista (em direção ao início do lista).

Esse algoritmo faz várias passagens pela lista. Cada passagem compara sucessivos pares de elementos. Se um par está em ordem crescente, os valores permanecem na mesma ordem. Se um par está em ordem decrescente, é realizada a troca entre os elementos do par.

Em cada passagem, o elemento maior será “levado” até o final da lista e, assim, iremos percorrer na primeira passagem todos os elementos. Na segunda passagem, não necessitamos percorrer todos, pois o maior estará no final e, então, percorremos até o penúltimo e assim sucessivamente até que a quantidade de elementos a percorrer seja igual a 1. Temos, então, o vetor ordenado.

Exemplo: dado o seguinte vetor desordenado como entrada, vamos acompanhar as etapas de execução do Bubble Sort:

Cada elemento do vetor é percorrido e a cada passagem são comparados os pares de elementos (o atual com o próximo). Caso o atual seja maior que o próximo, eles trocam de posição.

Repare que o vetor já está “um pouco mais ordenado” e o maior elemento ocupa a última posição. Mas ainda não está completamente ordenado. Esse processo então se repete n vezes até que o vetor esteja completamente ordenado.

No caso deste exemplo, apenas com duas rodadas foi possível ordenar completamente o vetor. Entretanto, no pior caso seria necessário executar um número de rodadas igual ao tamanho da lista, o que seria representado pela notação O(n²).

Ilustração do funcionamento do algoritmo Bubble Sort

Implementação do Bubble Sort

def bubble_sort(vetor: List[int]):
    trocou: bool = True
    while trocou:
        trocou = False
        for i in range(len(vetor)-1):
            if vetor[i] > vetor[i+1]:
                aux = vetor[i]
                vetor[i] = vetor[i+1]
                vetor[i+1] = aux
                trocou = True

Note que enquanto há trocas (trocou==true) o algoritmo continua iniciando uma nova rodada que irá varrer toda a lista em busca de trocar a posição dos pares de elementos que estão em ordem decrescente. Como o último elemento da lista sempre será o maior a cada rodada, pode-se retirá-lo da comparação para melhorar um pouco o tempo de execução. Para isso, usamos a variável ultimo,que recebe inicialmente como valor a posição do último elemento e é decrementada em menos 1 a cada rodada.