Bubble Sort descomplicado
- #PHP
O que é o Bubble Sort?
O Bubble Sort é um de vários algoritmos de ordenação que existem no mundo da programação, e é considerado um dos mais fáceis de entender e implementar. Sua função é ordenar os elementos de um determinado array.
O primeiro passo para entender este algoritmo, é entender o significado do seu nome "Bubble Sort", que pode ser traduzido como "Ordenação por Bolhas" (o que continua sem sentido). Mas então qual é o sentido por trás do nome? A explicação vem da forma como o algoritmo funciona: Os maiores valores vão "subindo" para o final do array, o que se assemelha com um copo de refrigerante, onde as bolhas sobem de baixo para cima no copo.
Como Funciona?
O processo de funcionamento do Bubble Sort pode se dividido em 3 passos:
- O algoritmo percorre o array inteiro e compara cada par de elementos que estão um do lado do outro.
- Na comparação de dois elementos, é verificado se o valor da esquerda é maior que o da direita. Se sim, os elementos trocam de posição, se não, o próximo par é verificado.
- Este processo vai se repetir até que todos os valores tenham sido colocados em suas posições corretas, e nenhuma troca precise ser feita mais.
Implementação em PHP comentada
<?php
function bubbleSort($nums) {
//$n é a quantidade de itens no array
$n = count($nums);
//Este laço externo irá se repetir até que não tenha mais trocas ou até que a condição de parada seja atendida
for($i=0; $i<$n-1; $i++) {
//variával que vai servir para verificar se alguma troca aconteceu ou não
$trocou = false;
//este laço interno irá verificar se um par de elementos precisa ser trocado ou não, e irá repetir isso com todos os pares até que todo o array tenha sido percorrido.
for($j=0; $j<$n-$i-1; $j++) {
//compara o par de elementos, e se o primeiro for maior, realiza a troca de posições;
if($nums[$j] > $nums[$j+1]) {
//variável temporária que armazena o valor do primeiro item do par
$temp = $nums[$j];
//o primeiro item do par passa a ter o valor do segundo
$nums[$j] = $nums[$j+1];
//o segundo item do par passa a ter o valor anteriormente armazenado do primeiro
$nums[$j+1] = $temp;
//indica que uma troca aconteceu
$trocou = true;
}
}
//quando não tiverem mais trocas a serem feitas, termina a execução do loop externo, o array já está ordenado!
if(!$trocou) {
break;
}
}
//devolve o array em sua forma ordenada
return $nums;
}
$nums = [64, 34, 25, 12, 22, 11, 90];
$resp = bubbleSort($nums);
echo "Array ordenado: " . implode(", ", $resp);
?>
Vantagens e Desvantagens do Bubble Sort
- Vantagens: Um algoritmo fácil de entender e de implementar;
- Desvantagens: É um algoritmo muito ineficiente em grande escala, pois sua complexidade de tempo é de O(n²);
Conclusão
O Bubble Sort é um ótimo algoritmo para se estudar com fins de aprendizagem em algoritmos e lógica de programação. Mostra conceitos básicos e importantes de se aprender para formar uma base sólida.
Se achou interessante o conceito deste algoritmo, recomendo também estudar tipos diferentes de algoritmos de ordenação, e também estudar sobre complexidade de tempo e espaço (mais conhecido como "Big O") para determinar qual estrutura é mais adequada para os seus projetos.
