Bubble Sort
💡 Entendendo a ideia
O algoritmo de ordenação Bubble Sort é um dos mais simples e fáceis de se compreender e implementar. Imagine um vetor não ordenado, como o exibido na imagem a seguir:
Para ordená-lo, o Bubble Sort irá comparar pares de posições, direcionando o maior elemento para o final do vetor. Isso acontecerá diversas vezes, resultando na ordenação do vetor.
🧑💻 Do conceito ao código
A implementação iterativa do Bubble Sort é bastante simples e envolve
void trocar(int *a, int *b){
int aux = *a;
*a = *b;
*b = aux;
}
void bubbleSort(int v[], int tam){
for (int i = 0; i < tam - 1; i++){
for (int j = 0; j < tam - i - 1; j++){
if (v[j] > v[j + 1]){
trocar(&v[j], &v[j+1]);
}
}
}
}
Agora, acompanhe a representação visual da execução do algoritmo, considerando um vetor de 4 posições.
Note que o vetor foi ordenado no meio da execução do algoritmo. Apesar disso, o algoritmo continua executando, já que ele não é "inteligente" a ponto de perceber que o vetor já está ordenado.
Versão melhorada
Podemos aprimorar o algoritmo para interromper o processo antes, se nenhuma troca for efetuada.
void bubbleSort(int v[], int tam){
for (int i = 0; i < tam - 1; i++){
bool trocou = false;
for (int j = 0; j < tam - i - 1; j++){
if (v[j] > v[j + 1]){
trocar(&v[j], &v[j+1]);
trocou = true;
}
}
if(!trocou) break;
}
}