Bubble Sort

O Bubble Sort é um dos algoritmos de ordenação mais populares entre os programadores e estudantes de computação. Contudo, sua popularidade é uma consequência da sua ineficiência, sendo um dos piores algoritmos de ordenação que existem.

O leitor poderia questionar: se ele é tão ruim, então por que estudá-lo? A resposta padrão seria 'para fins didáticos', entretanto essa não é uma resposta satisfatória.

Na prática, é bom aprender algoritmos ineficientes para entender o que os torna ruins e não repetir o 'mal' na hora de desenvolver algum programa ou criar algum algoritmo.

Este artigo apresenta o algoritmo do Bubble Sort e explica o seu funcionamento. No final do artigo, o leitor poderá ver a implementação do Bubble Sort em Java e em C.

Funcionamento do Bubble Sort

A ideia básica do algoritmo é realizar a troca de elementos em posições adjacentes (um ao lado do outro), de modo que os elementos com maior valor sejam posicionados no final do vetor (array) e os com menor valor sejam posicionados no início do vetor. Como exemplo, considere o vetor {19, 25, 23, 1}:

Vetor que será ordenado

Vamos comparar o elemento no índice 1 com o elemento imediatamente posterior, isto é, vamos comparar os valores 19 e 25. Como 19 é menor que 25, então não precisamos trocá-los de posição.

Continuando, vamos comparar o elemento do índice 2 com o elemento do índice 3. Como 25 é maior que 23, então trocamos suas posições

A comparação agora é entre 25 e 1, que resultará em outra troca

Observe que 25 era o maior elemento e, após percorrer o vetor, ele foi posicionado na última posição.

Vamos repetir o procedimento. Comparamos 19 com 23 (repare que voltamos ao primeiro índice), porém não há troca a ser realizada, pois 19 < 23. Comparamos 23 com 1 e, como 23 > 1, trocamos os valores de posição

Continuando

Vetor ordenado

Observe que o vetor está ordenado. Se quiser outro exemplo, você pode assistir ao vídeo a seguir

Link do vídeo: Bubble sort (exemplo animado)

Caso você tenha assistido ao vídeo, deve ter percebido que o Bubble Sort é um algoritmo um tanto bruto para realizar a ordenação de um vetor.

O Algoritmo do Bubble Sort

O algoritmo do Bubble Sort, em pseudocódigo, é apresentado a seguir

1. bubblesort(A[1...n], n)
2. |   para i ← 1 até n - 1
3. |   |   para j ← 1 até n - i
4. |   |   |   se(A[j] > A[j + 1])
5. |   |   |   |   trocar(A, j, j + 1)
6. |   |   |   fim_se
7. |   |   fim_para
8. |   fim_para
9. fim_bubblesort

Perceba que o algoritmo é relativamente simples. O método trocar(A, j, j + 1), na linha 5, troca o elementos das posições j e j+1 no vetor A. Perceba também que a indexação do vetor começa com 1, entretanto você não precisa se preocupar, pois os códigos no final do artigo são de linguagens de programação cuja indexação inicia com zero.

A complexidade do algoritmo anterior é $O(n^2)$ em qualquer caso. Veremos a seguir que é possível otimizar o algoritmo para que ele se torne $O(n)$ no melhor caso.

Se nenhuma troca for realizada após uma das iterações do laço externo (linha 2), então o vetor já estará ordenado, portanto não precisamos continuar executando o algoritmo. Para parar a execução, precisamos acrescentar uma variável e uma condição que servirão para verificar se alguma troca foi realizada em cada iteração. Em caso negativo, a execução do Bubble Sort deve ser interrompida. Uma das formas de fazer isso é com o algoritmo a seguir, que é basicamente uma versão otimizada do algoritmo anterior

1.  bubblesortOpt(A[1...n], n)
2.  |   para i ← 1 até n - 1
3.  |   |   flag ← 0
4.  |   |   para j ← 1 até n - i
5.  |   |   |   se(A[j] > A[j + 1])
6.  |   |   |   |   trocar(A, j, j + 1)
7.  |   |   |   |   flag ← 1
8.  |   |   |   fim_se
9.  |   |   fim_para
10. |   |   se(flag = 0)
11. |   |   |   parar laço //vetor ordenado
12. |   |   fim_se
13. |   fim_para
14. fim_bubblesortOpt

Nessa versão do Bubble Sort, se nenhuma troca for realizada no laço das linhas 4-9, então o valor da variável flag continuará zerado e o laço das linhas 2-13 será encerrado pelo comando 'parar laço' (em Java e C seria o comando break) do bloco 'se' das linhas 10-12.

Análise do Bubble Sort

O melhor caso do Bubble Sort ocorre quando o vetor está ordenado, pois o laço da linha 2 será executado uma única vez, quando i = 1. Dessa forma, a comparação na linha 5 será realizada n - 1 vezes. Portanto, a complexidade do Bubble Sort no melhor caso é $O(n)$.

O pior caso ocorre quando o vetor está ordenado em ordem decrescente, pois a comparação na linha 5 sempre será verdadeira, portanto o algoritmo irá realizar a troca na linha 6 em todas as iterações. A quantidade de iterações do laço da linha 2 é igual a n-1, que representamos pelo somatório

$$\sum_{i=1}^{n-1}(\ldots)$$

O laço da linha 5 realiza n-i iterações. Nesse caso, temos

$$\sum_{i=1}^{n-1}\left(\sum_{j=1}^{n-i} 1\right)$$

A fórmula nos fornece o número total de vezes que a comparação A[j] > A[j + 1] é realizada. Inicialmente, resolve-se o somatório entre parênteses

$$\sum_{i=1}^{n-1}(n-i)$$

Agora, resolvemos o somatório remanescente

$$\begin{align*}\sum_{i=1}^{n-1}(n-i)&= n(n-1)-\frac{n(n-1)}{2}\\&=\frac{1}{2}n(n-1)\\& =\frac{1}{2}n^2 - \frac{1}{2}n\\&=O(n^2)\end{align*}$$

Portanto, no pior caso, o Bubble Sort tem complexidade $O(n^2)$.

Finalmente, no caso médio, precisamos calcular a média dos custos entre todos os casos possíveis. O primeiro caso (de menor custo) ocorre quando o laço mais externo realiza uma única iteração e o último caso (de maior custo) ocorre quando o laço externo realiza o número máximo de iterações, isto é, n-1 iterações.

O que controla o número de iterações é a condição na linha 11. Como todos os casos são igualmente prováveis, isto é, todas as diferentes configurações do vetor de entrada têm a mesma probabilidade de ocorrer, então a probabilidade de cada caso é de $\cfrac{1}{n -1}$ e a média é dada por

$$\frac{1}{n -1}\sum_{k=1}^{n -1} (\ldots)$$

O valor entre parênteses é o custo total do algoritmo quando o laço da linha 2 executa k iterações

$$\frac{1}{n -1}\sum_{k=1}^{n -1} \left(\sum_{i=1}^{k}\sum_{j=1}^{n-i} 1\right)$$

Resolvendo a expressão, temos

$$\begin{align*}\frac{1}{n -1}\sum_{k=1}^{n -1} \left(\sum_{i=1}^{k}\sum_{j=1}^{n-i} 1\right)&=\frac{1}{n -1}\sum_{k=1}^{n -1} \left(\sum_{i=1}^{k}(n-i)\right)\\&=\frac{1}{n -1}\sum_{k=1}^{n -1}\left(nk-\frac{k(k+1)}{2}\right )\\&=\frac{n^2}{3}-\frac{n}{6}\\&=O(n^2)\end{align*}$$

Portanto, a complexidade no caso médio é $O(n^2)$. Eu pulei algumas etapas do cálculo anterior porque ficou muito grande.

Códigos

Nesta seção, apresento os códigos em Java e em C do Bubble Sort. Em ambos os casos, apresento a versão normal, que é $O(n^2)$ nos três casos, e a versão 'otimizada', que é $O(n)$ no melhor caso.

Algoritmo em Java

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

//Código por Henrique Felipe (GitHub: HenriqueIni) public class BubbleSort {     //Versão normal     public static void bubbleSort(int[] a){         if(a == null){             throw new NullPointerException("The array doesn't exist.");         }         for(int i = 0; i < a.length - 1; i++){             for(int j = 0; j < a.length - i - 1; j++){                 if(a[j] > a[j + 1]){                     int temp = a[j];                     a[j] = a[j + 1];                     a[j + 1] = temp;                 }             }         }     }     //versão 'otimizada' [O(n) no melhor caso]     public static void bubbleSortOpt(int[] a){         if(a == null){             throw new NullPointerException("The array doesn't exist.");         }         boolean flag = true;         for(int i = 0; i < a.length - 1 && flag; i++){             flag = false; //quando não há trocas, flag continuará false             for(int j = 0; j < a.length - i - 1; j++){                 if(a[j] > a[j + 1]){                     int temp = a[j];                     a[j] = a[j + 1];                     a[j + 1] = temp;                     flag = true; //troca realizada, flag true                 }             }         }     } }

Algoritmo em C

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

//Código por Henrique Felipe (GitHub: HenriqueIni)            #include <stdio.h> #include <stdlib.h> //Versão normal void bubbleSort(int a[], int n) {     int i, j;     for (i = 0; i < n - 1; i++) {         for (j = 0; j < n - i - 1; j++) {             if (a[j] > a[j + 1]) {                 int temp = a[j];                 a[j] = a[j + 1];                 a[j + 1] = temp;             }         }     } } //versão 'otimizada' [O(n) no melhor caso] void bubbleSortOpt(int a[], int n) {     int flag = 1;     int i, j;     for (i = 0; i < n - 1 && flag == 1; i++) {         flag = 0; //quando não há trocas, flag continuará 0         for (j = 0; j < n - i - 1; j++) {             if (a[j] > a[j + 1]) {                 int temp = a[j];                 a[j] = a[j + 1];                 a[j + 1] = temp;                 flag = 1; //troca realizada, flag = 1             }         }     } }