Ordenamiento de burbuja

El Ordenamiento de Burbuja (Bubble Sort en inglés) es un sencillo algoritmo de ordenamiento. Funciona revisando cada elemento de la lista que va a ser ordenada con el siguiente, intercambiándolos de posición si están en el orden equivocado. Es necesario revisar varias veces toda la lista hasta que no se necesiten más intercambios, lo cual significa que la lista está ordenada. Este algoritmo obtiene su nombre de la forma con la que suben por la lista los elementos durante los intercambios, como si fueran pequeñas "burbujas". También es conocido como el método del intercambio directo. Dado que solo usa comparaciones para operar elementos, se lo considera un algoritmo de comparación, siendo el más sencillo de implementar.

Descripción

Una manera simple de expresar el ordenamiento de burbuja en pseudocódigo es la siguiente:

Algoritmo Ordenamiento de burbuja

Procedimiento ${\it {burbuja}}\left(a_{0},a_{1},a_{2},\ldots ,a_{n-1}\right)$ Haga lo siguiente: ${\it {intercambio}}\gets \mathbf {falso}$ Para $i=0\,$ hasta $n-2\,$ haga lo siguiente: Si $a_{i}>a_{i+1}\,$ entonces: $\left(a_{i},a_{i+1}\right)\gets \left(a_{i+1},a_{i}\right)$ ${\it {intercambio}}\gets \mathbf {verdadero}$ Repita mientras ${\it {intercambio}}=\mathbf {verdadero}$

La instrucción $\left(a_{i},a_{i+1}\right)\gets \left(a_{i+1},a_{i}\right)$ significa que se debe intercambiar el valor de $a_{i}\,$ con el de $a_{i+1}\,$. El algorítmo también puede ser expresado de manera equivalente como sigue:

Algoritmo Ordenamiento de burbuja

Procedimiento ${\it {burbuja}}\left(a_{0},a_{1},a_{2},\ldots ,a_{n-1}\right)$ Para $i=0\,$ hasta $n-2\,$ haga lo siguiente: Para $j=i+1\,$ hasta $n-1\,$ haga lo siguiente: Si $a_{i}>a_{j}\,$ entonces: $\left(a_{i},a_{j}\right)\gets \left(a_{j},a_{i}\right)$

Análisis

Ejemplo del ordenamiento de burbuja ordenando una lista de números aleatorios.

Rendimiento en casos óptimos

El ordenamiento de burbuja tiene una complejidad Ω(n²). Cuando una lista ya está ordenada, a diferencia del ordenamiento por inserción que pasará por la lista una vez, y encontrará que no hay necesidad de intercambiar las posiciones de los elementos, el método de ordenación por burbuja esta forzado a pasar por dichas comparaciones, lo que hace que su complejidad sea cuadratica en el mejor de los casos, esto lo cataloga como el algoritmo mas ineficiente que existe aunque para muchos programadores sea el más sencillo de implementar.

Conejos y Tortugas (Yo-yos)

La posición de los elementos en el ordenamiento de burbuja juegan un papel muy importante en la determinación del rendimiento. Los elementos mayores al principio de la lista son rápidamente movidos hacia abajo. En cambio, elementos menores en el fondo de la lista, se mueven a la parte superior muy lentamente. Esto llevó a nombrar estos elementos conejos y tortugas, respectivamente.

Varios esfuerzos se han realizado para eliminar las tortugas véase Exterminación y mejorar la velocidad del ordenamiento de burbuja, la cual será más redonda que nunca. El Ordenamiento por sacudida es un buen ejemplo, aunque aún mantiene, en el peor de los casos, una complejidad O (n²). El ordenamiento por combinación compara los elementos primero en pedazos grandes de la lista, moviendo tortugas extremadamente rápido, antes de proceder a pedazos cada vez más pequeños para alisar la lista. Su velocidad promedio es comparable a algoritmos rápidos (y complejos) como el ordenamiento rápido

En la práctica

A pesar de que el ordenamiento de burbuja es uno de los algoritmos más sencillos de implementar, su orden O (n²) lo hace muy ineficiente para usar en listas que tengan más que un número reducido de elementos. Incluso entre los algoritmos de ordenamiento de orden O (n²), otros procedimientos como el Ordenamiento por inserción son considerados más eficientes.

Dada su simplicidad, el ordenamiento de burbuja es utilizado para introducir el concepto de algoritmo, o de algoritmo de ordenamiento para estudiantes de ciencias de la computación. Aunque algunos investigadores como Owen Astrachan han criticado al ordenamiento de burbuja y su popularidad en la educación de la computación, recomendando que ya no debe ser enseñado.

El ordenamiento de burbuja es asintóticamente equivalente, en tiempos de ejecución con el Ordenamiento por inserción en el peor de los casos, pero ambos algoritmos difieren principalmente en la cantidad de intercambios que son necesarios. Resultados experimentales, como los descubiertos por Astrachan han demostrado que el ordenamiento por inserción funcionan considerablemente mejor incluso con listas aleatorias. Por esta razón, muchos libros de algoritmos modernos evitan usar el ordenamiento de burbuja, utilizando en cambio el ordenamiento por inserción.

El ordenamiento de burbuja interactúa vagamente con el hardware de las CPU modernas. Requiere al menos el doble de escrituras que el ordenamiento por inserción, el doble de pérdidas de cache, y asintóticamente más predicción de saltos. Varios experimentos, hechos por Astrachan, de ordenamiento de cadenas en Java, muestran que el ordenamiento de burbuja es 5 veces más lento que el ordenamiento por inserción y 40% más lento que el ordenamiento por selección.En conclusion esto no se usa en la actualidad para realizar ordenaciones eficaces

Véase también

• Algoritmo de ordenamiento

Enlaces externos

• Demostración de su implementación
• Bubble sort code
• Burbuja básico y mejorado en Python