Você já precisou ordenar uma sequência de números ou outros elementos em uma determinada ordem? Se sim, você provavelmente usou algum algoritmo de ordenação para fazer isso. Um algoritmo de ordenação é um conjunto de instruções que define como organizar os elementos de uma sequência em uma ordem específica, como crescente ou decrescente.
Existem vários algoritmos de ordenação que podem ser usados para diferentes situações e necessidades. Neste post, vamos falar sobre um dos algoritmos de ordenação mais simples e conhecidos da ciência da computação: o Bubble Sort.
O Bubble Sort é um algoritmo de ordenação que pode ser aplicado em arrays e listas dinâmicas. Ele consiste em comparar pares de elementos adjacentes em uma sequência e trocar as suas posições se estiverem fora de ordem. O algoritmo repete esse processo até que a sequência esteja ordenada.
Neste post, vamos explicar como o Bubble Sort funciona, quais são as suas vantagens e desvantagens, e mostrar um exemplo em PHP. Acompanhe!
Quais são as vantagens e desvantagens do Bubble Sort?
O Bubble Sort tem algumas vantagens e desvantagens que devem ser consideradas na hora de escolher um algoritmo de ordenação. Vamos ver algumas delas:
Vantagens
- É um algoritmo simples de entender e implementar.
- É estável, ou seja, não altera a ordem relativa de elementos iguais.
- Funciona bem para sequências pequenas ou quase ordenadas.
- Não usa memória auxiliar, ou seja, é um algoritmo in-place.
Desvantagens
- É um algoritmo lento para sequências grandes ou desordenadas.
- Realiza muitas comparações e trocas desnecessárias, mesmo quando a sequência já está ordenada.
- Tem complexidade quadrática no pior e no caso médio, ou seja, o tempo de execução cresce muito rápido com o aumento do tamanho da entrada.
Quais são os outros algoritmos de ordenação mais usados?
O Bubble Sort é um dos algoritmos de ordenação mais simples, mas não é o mais eficiente. Existem outros algoritmos de ordenação que podem ser mais adequados para diferentes situações e necessidades. Alguns exemplos são:
- Selection Sort: seleciona o menor (ou maior) elemento da sequência e coloca na primeira (ou última) posição. Repete o processo para os elementos restantes até que a sequência esteja ordenada.
- Insertion Sort: insere cada elemento da sequência na posição correta em relação aos elementos já ordenados. Repete o processo até que a sequência esteja ordenada.
- Merge Sort: divide a sequência em duas metades, ordena cada metade recursivamente e combina as duas metades ordenadas em uma única sequência ordenada.
- Quick Sort: escolhe um elemento da sequência como pivô, particiona a sequência em duas subsequeências, uma com os elementos menores que o pivô e outra com os elementos maiores que o pivô. Ordena cada subsequeência recursivamente e combina as duas subsequeências ordenadas em uma única sequência ordenada.
- Heap Sort: transforma a sequência em uma estrutura de dados chamada heap, que é uma árvore binária completa onde cada nó é maior (ou menor) que seus filhos. Extrai o maior (ou menor) elemento da heap e coloca na última (ou primeira) posição da sequência. Repete o processo até que a heap esteja vazia e a sequência esteja ordenada.
Cada um desses algoritmos tem suas próprias vantagens e desvantagens, bem como suas próprias complexidades de tempo e espaço. Por isso, é importante conhecer as características de cada algoritmo e escolher o mais adequado para cada caso.
Como implementar o Bubble Sort em PHP?
Para mostrar como implementar o Bubble Sort em PHP, vamos usar um exemplo com uma sequência de números:
[8 ,5 ,2 ,6 ,9 ,3 ,1 ,4 ,0 ,7]
O objetivo é ordenar essa sequência em ordem crescente, ou seja, do menor para o maior elemento. Para isso, vamos usar uma função chamada bubble_sort que recebe um array como parâmetro e retorna o array ordenado. A função vai usar um laço while para repetir o processo até que não haja mais trocas, e um laço for para comparar cada elemento com o seu vizinho à direita e trocar se necessário. A função também vai usar uma variável chamada troca para indicar se houve alguma troca na última iteração. O código da função é:
<?php
function bubble_sort($array) {
$n = count($array); // obtém o tamanho do array
$troca = true; // inicializa a variável troca como verdadeira
while ($troca) { // enquanto houver troca
$troca = false; // assume que não houve troca
for ($i = 0; $i < $n - 1; $i++) { // percorre o array do início ao penúltimo elemento
if ($array[$i] > $array[$i + 1]) { // se o elemento atual for maior que o próximo
$aux = $array[$i]; // guarda o elemento atual em uma variável auxiliar
$array[$i] = $array[$i + 1]; // troca o elemento atual pelo próximo
$array[$i + 1] = $aux; // troca o próximo pelo elemento guardado na variável auxiliar
$troca = true; // indica que houve troca
}
}
$n--; // diminui o tamanho do array em uma unidade
}
return $array; // retorna o array ordenado
}
?>Para testar a função, vamos usar um código simples que cria um array com os números desordenados e imprime na tela antes e depois de aplicar a função bubble_sort:
<?php
$array = [8 ,5 ,2 ,6 ,9 ,3 ,1 ,4 ,0 ,7]; // cria um array com os números desordenados
echo "Array antes da ordenação:\n"; // imprime na tela uma mensagem
print_r($array); // imprime na tela o array
$array = bubble_sort($array); // aplica a função bubble_sort no array
echo "Array depois da ordenação:\n"; // imprime na tela outra mensagem
print_r($array); // imprime na tela o array
?>O resultado esperado é:
Array antes da ordenação:
Array
(
[0] => 8
[1] => 5
[2] => 2
[3] => 6
[4] => 9
[5] => 3
[6] => 1
[7] => 4
[8] => 0
[9] => 7
)
Array depois da ordenação:
Array
(
[0] => 0
[1] => 1
[2] => 2
[3] => 3
[4] => 4
[5] => 5
[6] => 6
[7] => 7
[8] => 8
[9] => 9
)Conclusão
Neste post, vimos o que é o algoritmo Bubble Sort e quais são as suas vantagens e desvantagens. Vimos também como ele funciona com exemplos práticos e como implementá-lo em PHP. Esperamos que este post tenha sido útil e esclarecedor para você. Se você gostou, compartilhe com seus amigos e deixe seu comentário. Até a próxima!