Clasificación de burbujas se considera uno de los algoritmos de clasificación más simples que funciona intercambiando repetidamente los elementos adyacentes si están en el orden incorrecto. Con un algoritmo de clasificación de burbujas, podrá ver que el elemento más grande (asumiendo que estamos ordenando de menor a mayor) «burbujeará» en la parte superior de la lista o matriz.

Ejemplo:
Suponga que queremos ordenar una lista o matriz de elementos en orden ascendente (de menor a mayor): Lista = (3,1,2)

Dado que no se produjo ningún intercambio, esto nos dice que la matriz es ¡ya ordenados en orden ascendente!

Mejor caso

Ahora intentemos este mismo algoritmo nuevamente, pero esta vez usando el mejor escenario, que es cuando los elementos ya están ordenados en el orden ( ascendente) nos gustaría.

Dado que no se produjo ningún intercambio, hemos terminado, y el algoritmo solo hizo 2 comparaciones y el número de elementos en la matriz llamaremos n = 3. Así que podemos ver que para n elementos, en el mejor de los casos, este algoritmo solo tomará n-1 comparaciones, n-1 = O (n)

El procedimiento o algoritmo que usamos es el siguiente:

Este algoritmo usa una bandera para saber si los elementos se han intercambiado o no , que permite que el algoritmo de clasificación de burbujas sea en el mejor de los casos O (n) en lugar de O (n²) como otra implementación de clasificación de burbujas.

El algoritmo anterior
Peor caso = O (n²)
Mejor caso = O (n)

Echemos un vistazo a una implementación diferente del algoritmo de clasificación de burbujas:

BUBBLESORT(A)
1 for i = 1 to A.length - 1
2 for j = A.length downto i + 1
3 if A < A
4 exchange A with A

El algoritmo anterior
Peor caso = O (n²)
Mejor caso = O (n²)

Peor caso

Ordenemos una matriz o lista = (3,2,1) este sería el peor caso donde la lista está en el orden completamente opuesto al que deseamos (en orden ascendente) usando el algoritmo anterior.

Primer paso:
(3,2,1) – > Compara los elementos 3 & 2
(2,3 , 1) – > Intercambiar 3 & 2 desde 2 < 3
( 2,3,1) – > Comparar los elementos 3 & 1
(2,1,3) – > Intercambiar 1 & 3 desde 1 < 3

Segunda pasada:
(2,1,3) – > Compara los elementos 2 & 1
(1,2,3) – > Intercambia 2 & 1 desde 1 < 2
(1,2,3) – > Compare el elementos 2 & 3
(1,2,3) – > No es necesario CAMBIAR desde 2 < 3

Ahora hemos terminado de recorrer ambos bucles, por lo que la matriz debe clasificarse en orden ascendente.

Observe que hicimos 4 comparaciones en el segundo ejemplo anterior, y el número de elementos en la matriz llamaremos ‘n’ = 3, por lo que el número de comparaciones realizadas es (n-1) ², y (n-1) ² = O (n²)

También es un gran libro que lo preparará para las entrevistas de codificación / programación: Cómo descifrar la entrevista de codificación. Le ayudará a familiarizarse con los algoritmos de clasificación y la resolución de problemas, así que asegúrese de comprobarlo.

¡Gracias por leer este artículo, espero que les sea útil a todos! Continúe aprendiendo, y si desea ver más videos de análisis de algoritmos, visite y suscríbase a mis canales de YouTube (randerson112358 & compsci112358)

Consulte lo siguiente para más contenido / videos sobre programación y análisis de algoritmos:

Canal de YouTube:
randerson112358: https://www.youtube.com/channel/UCaV_0qp2NZd319K4_K8Z5SQ

compsci112358:

Sitio web:

Tutoriales en video sobre la relación de recurrencia:

Tutorial en video sobre análisis de algoritmos:

Twitter: