Explicação da classificação por bolha
Assim como as bolhas sobem da parte inferior de um copo, a classificação de bolhas é um algoritmo simples que classifica uma lista, permitindo que valores mais baixos ou mais altos borbulhem no topo. O algoritmo percorre uma lista e compara valores adjacentes, trocando-os se não estiverem na ordem correta.
Com uma complexidade de pior caso de O (n ^ 2), a classificação por bolhas é muito lenta em comparação com outros algoritmos de classificação, como a classificação rápida. A vantagem é que ele é um dos algoritmos de classificação mais fáceis de entender e codificar do zero.
Exemplo:
let arr = [4, 2, 6, 3, 9]; let sorted = false while(!sorted) { sorted = true for(var i = 0; i < arr.length; i++) { if(arr[i] < arr[i - 1]) { let temp = arr[i]; arr[i] = arr[i - 1]; arr[i - 1] = temp; sorted = false; } } }Primeira passagem pela lista:
- Começando com
[4, 2, 6, 3, 9], o algoritmo compara os dois primeiros elementos na matriz, 4 e 2. Ele os troca porque 2 <4:[2, 4, 6, 3, 9] - Ele compara os próximos dois valores, 4 e 6. Como 4 <6, eles já estão em ordem, e o algoritmo segue em frente:
[2, 4, 6, 3, 9] - Os próximos dois valores também são trocados porque 3 <6:
[2, 4, 3, 6, 9] - Os dois últimos valores, 6 e 9, já estão em ordem, portanto, o algoritmo não os troca.
Segunda passagem pela lista:
- 2 <4, portanto, não há necessidade de trocar posições:
[2, 4, 3, 6, 9] - O algoritmo troca os próximos dois valores porque 3 <4:
[2, 3, 4, 6, 9] - Sem troca como 4 <6:
[2, 3, 4, 6, 9] - Novamente, 6 <9, então nenhuma troca ocorre:
[2, 3, 4, 6, 9]
A lista já está classificada, mas o algoritmo de classificação de bolha não percebe isso. Em vez disso, ele precisa completar uma passagem inteira pela lista sem trocar nenhum valor para saber se a lista está classificada.
Terceira passagem pela lista:
[2, 4, 3, 6, 9]=>[2, 4, 3, 6, 9][2, 4, 3, 6, 9]=>[2, 4, 3, 6, 9][2, 4, 3, 6, 9]=>[2, 4, 3, 6, 9][2, 4, 3, 6, 9]=>[2, 4, 3, 6, 9]
Claramente, a classificação por bolhas está longe de ser o algoritmo de classificação mais eficiente. Ainda assim, é simples envolver sua cabeça e implementar você mesmo.
Agora vá se servir de uma bebida gelada e espumante - você merece.
