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.