28 de dezembro de 2023
Algoritmo: Bubblesort
Algoritmos
Lógica
Bubble sort é um algoritmo muito simples para ordenação. Ele itera sobre uma lista comparando dois itens de cada vez. No caso de ordenação crescente, se o item da esquerda for maior que o da direita, eles trocam de lugar. A cada iteração completa pela lista, o maior número estará no final, e, portanto, não precisamos mais compará-lo. Então reiteremos sobre a mesma lista menos o último, e depois menos os dois últimos e depois menos os três, e… você entendeu. Em algum momento não vão sobrar itens para comparar e a lista estará ordenada.
Implementação
Uma maneira de implementar esse algoritmo na linguagem C pode ser assim:
1void bubble_sort(int numbers[], int length)
2{
3 for (int i = 0; i < length - 1; i++) // {1}
4 {
5 for (int j = 0; j < length - i - 1; j++) // {2}
6 {
7 if (numbers[j] > numbers[j + 1]) // {3}
8 {
9 swap(&numbers[j], &numbers[j + 1]); // {4}
10 }
11 }
12 }
13};{1} Usaremos esse loop para ir “limitando” a execução das comparações. Cada vez que percorremos toda a lista, i é somado 1 e podemos usar i para limitar o tamanho percorrido no segundo loop {2}. Como demonstrado mais abaixo em “bubble_sort_experimental”, o maior elemento não ordenado da lista é colocado no final a cada iteração.
{3} Se o item que estamos comparando for maior que o seu próximo, ele está na posição errada. Então permutaremos suas posições {4}.
Executando
1#include <stdio.h>
2#include "src/bubble_sort.h"
3#include "utils/print_array.h"
4
5int main()
6{
7 int unsorted[] = {666, 1, 2, 3, 4, 5, 6};
8 int length = sizeof(unsorted) / sizeof(unsorted[0]);
9
10 bubble_sort(unsorted, length);
11 print_array(unsorted, length);
12}Vamos visualizar o que acontece com o maior elemento quando ele está no começo da lista:
1void bubble_sort_experimental(int numbers[], int length)
2{
3 int first_item = numbers[0];
4 for (int i = 0; i < length - 1; i++)
5 {
6 printf("%d° iteration \\n", i + 1);
7 for (int j = 0; j < length - i - 1; j++)
8 {
9 if (numbers[j] > numbers[j + 1])
10 {
11 if (first_item == numbers[j])
12 {
13 printf("the first item %d swap position with %d \\n", first_item, numbers[j + 1]);
14 }
15 swap(&numbers[j], &numbers[j + 1]);
16 }
17 }
18 }
19};Executando:
11° iteration
2the first item 666 swap position with 1
3the first item 666 swap position with 2
4the first item 666 swap position with 3
5the first item 666 swap position with 4
6the first item 666 swap position with 5
7the first item 666 swap position with 6
82° iteration
93° iteration
104° iteration
115° iteration
126° iteration
131 2 3 4 5 6 666Ainda na primeira iteração, 666 foi para o final e podemos desconsiderá-lo.
Implementação recursiva
Podemos também fazer algo recursivo:
1void bubble_sort_recursive(int numbers[], int length)
2{
3 if (length < 1) // {1}
4 return;
5
6 for (int i = 0; i < length - 1; i++) // {2}
7 {
8 if (numbers[i] > numbers[i + 1])
9 {
10 swap(&numbers[i], &numbers[i + 1]);
11 }
12 }
13 bubble_sort_recursive(numbers, length - 1); // {3}
14};{1} Se a lista está vazia não tem o que comparar.
{2} Nesse caso, é igual à primeira implementação: iterar, comparar e, se necessário, trocar de lugar.
{3} Por fim, passamos a mesma função para a lista menos o último elemento.
Tempo de execução
O seu tempo de execução para o pior caso é O(n²), porém funciona bem com listas parcialmente ordenadas.
Referência
T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduction to Algorithms, 3rd edition, MIT Press, 2009.