Preciso estudar sempre: Bolhas no tanque

Bem-vindos ao blog Preciso Estudar Sempre. Meu nome é João Paulo Maida e minha paixão é estudar.

Este é o primeiro post da nossa série sobre algoritmos de ordenação e vamos começar com aquele algoritmo mais primordial que nos acompanhou em todo o período da faculdade, o Bubble Sort. Se você ainda não passou por isso, relaxe pois, passará. Se você já passou e não entendeu como ele funciona, agora é o momento da decisão.

O estudo que faremos aqui envolverá a construção do algoritmo em Java e alguns experimentos. Não usaremos ferramentas de desenvolvimento ultra modernas, um simples editor de texto bastará.

Qual é a lógica por trás desse algoritmo ? É simples, sua lógica consiste na troca da posições dentro do array de elemento por elemento, analisando quem tem o maior valor. O elemento de maior valor vai sendo movimentado para o fundo do array, até encontrar alguém maior que ele. Caso encotnre, o antigo maior valor pára de ser movimentado e o novo maior valor começa a ser movimentado para o fundo do array, respeitando a regra mencionada acima

Ficou confuso ? Vamos entender melhor.

Figura 1 - Funcionamento do algoritmo Bubble Sort

No gif animado acima é possível ver quer os elementos são avaliados par a par. Se o primeiro elemento do par for maior que o segundo ele é trocado de lugar, por exemplo os valores 6 e 5.

Figura 2 - Primeiro par escolhido

Após a troca de lugar, é avaliado o segundo par: 6 e 3.

Figura 3 - Segundo par escolhido

As trocas são realizadas somente se o primeiro elemento for maior que o segundo. Caso não seja, um novo par é escolhido. No gif animado é possível ver que em um determinado momento, o 6 forma par com o 8 mas, 6 não é maior que 8 logo, ele não é trocado e um novo par é feito. Todo este processo é repetido até que o array esteja ordenado.

Agora sim, temos tudo o que precisamos para construir nosso algoritmo.

      public void sort(int[] array, int tamanho){  
           int aux;  
   
           for(int i=tamanho-1; i >= 1; i--) {   
                for(int j=0; j < i ; j++) {  
                     if(array[j]>array[j+1]) {  
                          aux = array[j];  
                          array[j] = array[j+1];  
                          array[j+1] = aux;  
                     }  
                }  
           }  
      }

O algoritmo é bem simples e tem complexidade O(n²) no pior caso. O segundo for executa uma varredura no sentido início - fim, avaliando se o primeiro elemento da dupla é maior que o segundo. O responsável pela troca de posições é o bloco de código dentro do if. O primeiro for trabalha de forma fim - início a fim de otimizar o algoritmo visto que, uma vez que o elemento de maior valor é jogado para o fim do array, não existe motivo para que uma dupla seja composta com esse valor. É possível ver isso acontecendo no gif animado, no momento em que o 8 (maior valor) é jogado para o fim do array.

Ótimo !!! Atingimos mais uma etapa. Primeiramente, entendemos a lógica do algoritmo e logo em seguida, vimos uma possível implementação. Para fechar com perfeição, vamos fazer algumas análises de tempo de processamento.

Dadas as situações testadas abaixo:

Figura 4 - Testes feitos para medir a execução do algoritmo

As quais geraram o seguinte gráfico:

Figura 5 - Gráfico de quantidade de palavras por tempo

É possível notar que conforme o número de elementos cresce de forma quadrática, o tempo do algoritmo cresce seguindo a família do 100, ou seja, 100 vezes, 200 vezes, etc.. Se continuássemos os testes para dez mil ou cem mil iríamos notar um aumento ainda maior no tempo de execução. Tal algoritmo, se aplicado a situações da vida real onde, a dimensão do problema pode ser maior ou menor que os testados aqui, pode gerar um certo atraso ou não, na execução do programa como um todo.

E com isso, terminamos o nosso estudo sobre o algoritmo Bubble Sort. Espero que você tenha gostado. Caso note alguma anomalia nos testes realizados, deixe sua contribuição nos comentários.

Para baixar o algoritmo, clique aqui.

Dúvidas !? Sugestões ?! Críticas ou elogios ?!

Deixe aí nos comentários ou na nossa página do facebook.

Facebook: https://www.facebook.com/precisoestudarsempre/

Referências:
Comparison Sorting Algorithms - https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.htmlA Comparative Study between Various Sorting Algorithms - http://paper.ijcsns.org/07_book/201503/20150302.pdf
Sorting Algorithm Animations - http://www.sorting-algorithms.com/
Bubble sort - https://pt.wikipedia.org/wiki/Bubble_sort