5.7. O Bubble Sort¶

O bubble sort realiza múltiplas passagem por uma lista. Ele compara itens adjacentes e troca aqueles que estão fora de ordem. Cada passagem pela lista coloca o próximo maior valor na sua posição correta. Em essência, cada item se desloca como uma “bolha” para a posição à qual pertence.

A Figura 1 mostra a primeira passagem de um bubble sort. Os itens sombreados são aqueles que estão sendo comparados para verificar se estão fora de ordem. Se existem n itens na lista, então existem \(n-1\) pares de itens que precisam ser comparados na primeira passagem. É importante observar que o maior valor na lista esteja em alguma comparação, ele será continuamente empurrado até o fim da passagem.

Figura 1: bubbleSort: A Primeira Passagem¶

No começo da segunda passagem, o maior valor agora está ordenado. Ainda existem \(n-1\) itens para serem ordenados, o que significa que teremos \(n-2\) pares de comparação. Como cada passagem colocar o próximo maior valor encontrado no lugar certo, o número total de passagens necessárias será \(n-1\). Depois de completar \(n-1\) passagens, o menor item estará na posição correta e nenhum processamento adicional será necessário. O ActiveCode 1 mostra a função bubbleSort completa. Ela recebe uma lista como parâmetro e a modifica, trocando os itens conforme a necessidade.

A operação de troca, às vezes chamada de “swap”, é ligeiramente diferente em Python, quando comparada a outras linguagens de programação. Tipicamente, a troca de dois elementos numa lista requer o uso de uma variável para armazenamento temporário. O trecho de código abaixo

temp = alist[i]
alist[i] = alist[j]
alist[j] = temp

irá trocar os i-ésimos com os j-ésimos itens na lista. Sem a variável de armazenamento temorário, um dos valores seria sobrescrito.

Em Python, porém, é possível realizar atribuições simultâneas. A expressão a,b=b,a irá resultar em duas atribuições sendo feitas ao mesmo tempo (see Figure 2). Usando atribuições simultâneas, a troca pode ser feita em uma única linha.

As linhas 5-7 em ActiveCode 1 realizam a troca entre os itens \(i\) e \((i+1)\) utilizando o procedimento de três passos descrito anteriormente. Note que poderíamos ter usado a atribuição simultânea para trocar os itens.

Figura 2: Trocando Dois Valores em Python¶

O exemplo de activecode a seguir mostra a função bubbleSort completa utilizando a lista mostrada acima.

A animação abaixo mostra o bubbleSort em ação.

Para analisar o bubble sort, devemos perceber que independente de como os itens estão dispostos na lista inicial, \(n-1\) passagens serão feitas para ordenar uma lista de tamanho n. A Tabela 1 mostra o número de comparações para cada passagem. O número total de comparações é a soma dos primeiros \(n-1\) inteiros. Lembre-se de que a soma dos primeiros n inteiros é \(\frac{1}{2}n^{2} + \frac{1}{2}n\). A soma dos primeiros \(n-1\) inteiros é \(\frac{1}{2}n^{2} + \frac{1}{2}n - n\), que é \(\frac{1}{2}n^{2} - \frac{1}{2}n\). Ou seja, continuamos com \(O(n^{2})\) comparações. No melhor caso, se a lista já estiver ordenada, nenhuma mudança será feita. Contudo, no pior caso, cada comparação resultará numa troca. Na média, trocamos metade das vezes.

O bubble sort com frequência é considerado o método de ordenação mais ineficiente, já que ele precisa realizar a troca de itens sem saber qual será sua posição final. Essas trocas “desnecessárias” são muito custosas. Contudo, justamente por realizar passagens pela porção desordenada da lista, o bubble sort consegue fazer o que a maioria dos outros algoritmos de ordenação não consegue. Em particular, se durante uma passagem não houver trocas, então sabemos que a lista está ordenada. O bubble sort pode ser modificado para terminar antes se descobrir que a lista ficou ordenada. Isso significa que para listas que requerem apenas algumas passagens, o bubble sort pode ter a vantagem de reconhecer a lista ordenada e parar. O ActiveCode 2 mostra essa modificação, a qual é comumente chamada de short bubble.