Explicación de la clasificación de burbujas

Al igual que la forma en que las burbujas se elevan desde el fondo de un vaso, la clasificación de burbujas es un algoritmo simple que ordena una lista, lo que permite que los valores más bajos o más altos suban a la parte superior. El algoritmo recorre una lista y compara valores adyacentes, intercambiándolos si no están en el orden correcto.

Con una complejidad en el peor de los casos de O (n ^ 2), la clasificación de burbujas es muy lenta en comparación con otros algoritmos de clasificación como clasificación rápida. La ventaja es que es uno de los algoritmos de clasificación más fáciles de entender y codificar desde cero.

Ejemplo:

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; } } }

Primero pase por la lista:

  • Comenzando con [4, 2, 6, 3, 9], el algoritmo compara los dos primeros elementos de la matriz, 4 y 2. Los intercambia porque 2 <4:[2, 4, 6, 3, 9]
  • Compara los dos valores siguientes, 4 y 6. Como 4 <6, estos ya están en orden, y el algoritmo continúa: [2, 4, 6, 3, 9]
  • Los dos valores siguientes también se intercambian porque 3 <6: [2, 4, 3, 6, 9]
  • Los dos últimos valores, 6 y 9, ya están en orden, por lo que el algoritmo no los intercambia.

Segunda pasada por la lista:

  • 2 <4, por lo que no es necesario intercambiar posiciones: [2, 4, 3, 6, 9]
  • El algoritmo intercambia los siguientes dos valores porque 3 <4: [2, 3, 4, 6, 9]
  • Sin intercambio como 4 <6: [2, 3, 4, 6, 9]
  • Nuevamente, 6 <9, por lo que no se produce ningún intercambio: [2, 3, 4, 6, 9]

La lista ya está ordenada, pero el algoritmo de clasificación de burbujas no se da cuenta de esto. Más bien, necesita completar una pasada completa a través de la lista sin intercambiar ningún valor para saber que la lista está ordenada.

Tercera pasada por la 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, la clasificación de burbujas está lejos de ser el algoritmo de clasificación más eficiente. Aún así, es fácil de entender e implementarlo usted mismo.

Ahora sírvete una bebida fría y burbujeante, te lo mereces.