Ordenamiento de burbuja
El ordenamiento de burbuja es el algoritmo de ordenamiento más sencillo de describir: compara dos vecinos, intercámbialos si están en el orden equivocado y repite. Es lento con listas largas, pero cada paso es fácil de seguir, y por eso es el primer algoritmo clásico para ver en acción.
La idea
Recorre la lista de izquierda a derecha y mira cada par de vecinos. Si el valor de la izquierda es mayor que el de la derecha, intercámbialos. Al llegar al final, el mayor valor ha sido llevado hasta el último lugar, igual que una burbuja sube a la superficie. Ese recorrido se llama pasada. Repite las pasadas hasta que la lista esté ordenada.
Un ejemplo
Toma 5, 1, 4, 2, 8. La primera pasada compara 5 y 1 y los intercambia, luego 5 y 4 (intercambio), 5 y 2 (intercambio) y 5 y 8 (sin intercambio): 1, 4, 2, 5, 8. El 8 ya está en su lugar definitivo. La segunda pasada compara 1 y 4 (sin intercambio), 4 y 2 (intercambio) y 4 y 5 (sin intercambio): 1, 2, 4, 5, 8. La tercera pasada no hace ningún intercambio, así que la lista está ordenada: 9 comparaciones y 4 intercambios.
Por qué cada pasada coloca un valor más
Durante una pasada, el mayor valor visto hasta el momento siempre se arrastra: en cuanto la pasada lo alcanza, cada comparación lo mueve un lugar más a la derecha. Así, la primera pasada pone el mayor valor al final, la segunda el segundo mayor justo antes, y así sucesivamente. Tras la pasada k, los últimos k lugares son definitivos, y la siguiente pasada puede detenerse un lugar antes. Por eso las pasadas son cada vez más cortas.
Los intercambios igualan a las inversiones
Una inversión es un par de valores en el orden equivocado: un valor mayor en algún lugar antes de uno menor. Intercambiar dos vecinos desordenados elimina exactamente una inversión y no crea ninguna. Por eso el ordenamiento de burbuja hace exactamente tantos intercambios como inversiones tiene la lista inicial, sea cual sea el orden de las comparaciones. Una lista ordenada no tiene ninguna; una lista invertida de n valores tiene n(n − 1)/2, el máximo posible.
La parada anticipada y el coste
Si una pasada entera no hace intercambios, todos los vecinos están en orden y la lista está ordenada. Comprobarlo permite al ordenamiento de burbuja terminar una lista ordenada en una sola pasada de n − 1 comparaciones. En el peor caso sigue necesitando n − 1 pasadas y n(n − 1)/2 comparaciones, y de media el número de intercambios es n(n − 1)/4. Ambos crecen con n², así que duplicar la lista hace que la ordenación tarde unas cuatro veces más.
El ordenamiento de burbuja es estable: los valores iguales nunca se intercambian, así que conservan su orden. Ordena en el sitio, sin memoria adicional. El ordenamiento por inserción comparte esas propiedades y suele necesitar menos pasos, y el ordenamiento por mezcla y el quicksort tardan un tiempo proporcional a n log n, mucho menos en listas largas.
Explóralo
Abre la app y pulsa Reproducir, o pulsa Paso para avanzar de comparación en comparación. Los dos valores que se comparan aparecen resaltados, un intercambio se muestra en su propio color y los valores que ya están en su sitio se vuelven verdes. Prueba una lista invertida para ver el peor caso, una casi ordenada para ver cómo la parada anticipada termina la ordenación tras pocas pasadas, o escribe los números del ejemplo anterior.
Preguntas frecuentes
¿Cuál es la complejidad temporal del ordenamiento de burbuja?
O(n²) en el peor caso y en el caso medio: hasta n(n − 1)/2 comparaciones para n valores. Con la parada anticipada, una lista ya ordenada tarda O(n), una sola pasada. Solo necesita O(1) de memoria adicional.
¿Es estable el ordenamiento de burbuja?
Sí. Solo intercambia dos vecinos cuando el de la izquierda es estrictamente mayor, así que los valores iguales nunca se adelantan entre sí y conservan su orden original.
¿Qué diferencia hay entre el ordenamiento de burbuja y el ordenamiento por inserción?
Ambos intercambian vecinos y ambos hacen tantos intercambios como inversiones hay. El ordenamiento de burbuja hace pasadas completas sobre la parte sin ordenar; el ordenamiento por inserción desplaza cada nuevo valor hacia atrás solo lo necesario, así que suele hacer menos comparaciones, sobre todo en listas casi ordenadas.
¿Cuándo conviene usar el ordenamiento de burbuja?
Sobre todo para enseñar, y para listas muy cortas en las que la sencillez importa más que la velocidad. Para todo lo demás, la función de ordenación integrada en tu lenguaje de programación es mucho más rápida.
¿Listo para probarlo?
Abre PictorX en tu navegador: sin instalación ni tarjeta de crédito para empezar.
Prueba el ordenamiento de burbuja