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.
Passagem |
Comparações |
---|---|
1 |
\(n-1\) |
2 |
\(n-2\) |
3 |
\(n-3\) |
… |
… |
\(n-1\) |
\(1\) |
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.
Autoavaliação
- [1, 9, 19, 7, 3, 10, 13, 15, 8, 12]
- Esta resposta representa três trocas. Uma passagem significa que você continua realizando trocas durante todo o tempo até o fim da lista.
- [1, 3, 7, 9, 10, 8, 12, 13, 15, 19]
- Muito bem.
- [1, 7, 3, 9, 10, 13, 8, 12, 15, 19]
- O bubble sort continua a trocar os número até a posição do índice passnum. Mas lembre-se de que passnum começa com o tamanho da lista - 1.
- [1, 9, 19, 7, 3, 10, 13, 15, 8, 12]
- Você fez a ordenação por inserção, não o bubble sort.
Q-2: Suponha que você tenha a seguinte lista de números para ordenar: <br> [19, 1, 9, 7, 3, 10, 13, 15, 8, 12] qual lista representa a lista parcialmente ordenada depois de três passagens completas do bubble sort?