Otro algoritmo de ordenación importante es el que se conoce como ordenamiento de burbuja, el cual recibe este nombre porque el efecto del algoritmo simula el movimiento de una burbuja hacia la superficie, sólo que aquí no es una burbuja sino el número más pequeño y no flota hacia la superficie, sino a la cabeza de la lista. Funciona así:
Repetidamente recorre la lista y compara cada posible pareja de números; si están en el orden equivocado, se intercambian. Cuando recorre la lista y no hace ningún intercambio, se detiene porque la lista está ordenada. ¿Sorprendente, verdad? Vale la pena intentarlo con la lista del ejemplo anterior: 31 25 12 22 11. Va la secuencia de operaciones:
31 25 12 22 11, se comparan 31 y 25; se intercambian
25 31 12 22 11, ahora 31 y 12; se intercambian
25 12 31 22 11, 31 y 22; se intercambian
25 12 22 31 11, 31 y 11; se intercambian
25 12 22 11 31…
12 25 22 11 31
12 22 25 11 31
12 22 11 25 31; aquí se comparan 25 y 31, pero no hay cambio
12 22 11 25 31
… etcétera.
El ordenamiento de burbuja también tiene complejidad cuadrática. Aquí cabe una pausa para reflexionar sobre lo que se ha visto respecto a los algoritmos de ordenamiento.
Los algoritmos que se revisaron tienen similitudes: son fáciles y, debido a su complejidad, del orden de n2 es fácil percatarse de que son mejores en comparación con el viejo conocido n!; obsérvese que si empleamos un segundo por comparación, ordenar una lista de 20 elementos nos toma casi siete minutos y no cinco veces la edad del universo, como en el caso del factorial. Pero se puede lograr algo aún mejor.
