py012 - Algoritmo BubbleSort Python

Resumen

Aprender los algoritmos de Python relacionados con inteligencia artificial, combinatoria y teoría de grafos.

Publicación
Inteligencia Artificial, Combinatoria, Grafos, Algoritmos en Python
Fecha

El ordenamiento burbuja, del inglés (BubbleSort), es un popular algoritmo que funciona intercambiando pares de elementos adyacentes previamente desordenados. La invariante del algoritmo es que al final de la i-ésima interación, el i-ésimo elemento de la lista está en la posición correcta, en la lista ordenada. En este escenario i puede tomar valores 0, 1, ….m n done n es la cantidad de elementos a ordenar.

Aquí va un ejemplo:

5 2 3 1 4

Se realizará un recorrido desde la última posición hasta la primera, intercambiando pares de elementos adyacentes, si el elemento de la derecha es menor.

Para llevar el segundo elemento más pequeño a la segunda posición de la lista, se procede de igual forma pero haciendo el recorrido desde la última posición hasta la segunda. Así sucesivamente para que cada elemento quede en su posición ordenada.



El ciclo exterior for recorre la lista de izquierda a derecha, el ciclo interior while realiza el recorrido de derecha a izquierda, llegando hasta el índice actual del primer ciclo que lo contiene.

La sentencia if compara elementos adyacentes y lo intercambia en caso que su condición se satisfaga.

Siendo sencillo y poco eficiente, carece de utilidad práctica, cualquier otro algoritmo de ordenamiento puede ganar en eficiencia.