Ordenamiento por burbuja
Algoritmo de ordenación elemental que compara y troca elementos adyacentes. Muy didáctico y simple, pero ineficiente en grandes conjuntos; tiene variantes adaptativas y aplicaciones educativas.
Resumen
El ordenamiento por burbuja es un método de ordenación sencillo y fácil de comprender. Funciona comparando pares de elementos adyacentes y, si están en el orden equivocado, intercambiándolos. Repite este proceso hasta que la lista queda ordenada. Por su simplicidad se usa con frecuencia para presentar conceptos básicos de ordenación y estructuras de datos; para más información técnica sobre técnicas de ordenación consulte algoritmos de ordenación.
Galería de imágenes
2 Imágenes
Cómo funciona
En cada pasada por la lista, el algoritmo recorre los elementos desde el principio hasta el final (o viceversa), comparando cada par contiguo. Si un par está desordenado, se realiza un intercambio (swap). Tras una pasada completa, el elemento más grande de los no ordenados queda colocado en su posición final, como si burbujease hasta la superficie. El proceso se repite reduciendo el área a examinar hasta que no hay intercambios.
Propiedades y complejidad
- Estabilidad: El algoritmo es estable: preserva el orden relativo de elementos iguales.
- Almacenamiento: Es in-place: sólo necesita memoria constante adicional.
- Complejidad temporal: En el peor y caso promedio suele ser cuadrática (O(n^2)), por lo que es lento para grandes n.
- Adaptativo: En su forma básica no es muy adaptativo, pero variantes con detección de orden pueden terminar antes si la lista está casi ordenada.
Variantes y mejoras
Existen modificaciones que mejoran el comportamiento práctico sin cambiar la complejidad asintótica: una comprobación de intercambios para detenerse si la lista queda ordenada, y la versión bidireccional conocida como "cocktail shaker" o ordenamiento por sacudida, que recorre la lista en ambos sentidos en cada iteración. Estas variantes reducen el número de pasadas en casos parcialmente ordenados.
Historia y uso
El nombre evoca el movimiento de las burbujas en un líquido: los elementos «suben» hasta su posición final. Aunque no es la opción más eficiente para aplicaciones de producción con conjuntos extensos, su implementación mínima y claridad conceptual lo han convertido en un recurso didáctico clásico en cursos de programación y en ejemplos de análisis de algoritmos. También se emplea ocasionalmente en sistemas con restricciones extremas de memoria y listas muy cortas.
Comparaciones y notas finales
Frente a algoritmos más complejos como quicksort o mergesort, el ordenamiento por burbuja ofrece desventajas en rendimiento pero ventajas en simplicidad y previsibilidad. Para entender las ideas de comparación, intercambio, estabilidad y optimización temprana resulta muy útil. La metáfora visual de que cada elemento "burbujea" hasta su lugar ayuda a asimilar su comportamiento; ver una animación puede aclararlo aún más (ver ilustración).
Algoritmo
El algoritmo compara pares de elementos en una lista. Los elementos que componen los pares están uno al lado del otro. Empezando por un extremo de la lista, los dos elementos de cada par se comparan entre sí en orden. Esto significa, por ejemplo, que se comparan el primer y el segundo elemento, luego el segundo y el tercero, y luego el tercero y el cuarto, y así sucesivamente. Si los elementos de la pareja actual están desordenados, los dos elementos cambian de lugar. Este proceso -de comparar dos elementos- se realiza una y otra vez, hasta que toda la lista está ordenada. La lista está ordenada cuando no hay más pares que deban intercambiarse.
En el mejor de los casos, cuando la lista ya estaba ordenada antes de ejecutar el algoritmo, la complejidad del algoritmo es O(n) (notación Big O). En el peor de los casos, en el que la lista empieza a estar ordenada a la inversa, O(n²).
Implementación
En un lenguaje de programación imperativo, la ordenación de burbujas puede implementarse utilizando una variable de bandera y haciendo un bucle a través de los elementos de la matriz:
- Establece la bandera
ordenada. - Empezando por un extremo, considera cada par de elementos vecinos de un vector uno tras otro (en su orden).
- Si los elementos de un par están desordenados, intercámbialos y borra la bandera
ordenada. - Repita los pasos anteriores hasta que
la ordenaciónquede fijada.
Alternativamente, dado que el mayor valor asciende al índice más alto dentro de la primera iteración y luego ha alcanzado su posición final a la derecha, dos bucles for anidados uno dentro del otro ordenan también el vector:
Páginas relacionadas
- Clasificación por inserción
- Ordenación de la selección
Preguntas y respuestas
P: ¿Qué es la clasificación por burbujas?
R: La ordenación por burbujas es un algoritmo de ordenación simple.
P: ¿Por qué se suele enseñar la ordenación burbuja a los nuevos alumnos?
R: La ordenación por burbujas es fácil de entender, por lo que se suele enseñar a los nuevos alumnos.
P: ¿Es eficiente la ordenación burbuja comparada con otros algoritmos de ordenación?
R: La ordenación burbuja no es tan eficiente como otros algoritmos de ordenación.
P: ¿Por qué la ordenación burbuja se llama ordenación burbuja?
R: El nombre de ordenación por burbujas proviene del hecho de que cada elemento de la lista "burbujea" hacia donde debe ir, como las burbujas en el agua.
P: ¿La ordenación por burbujas es adecuada para grandes conjuntos de datos?
R: La ordenación por burbujas no es adecuada para grandes conjuntos de datos debido a su ineficacia.
P: ¿Cuál es el proceso de clasificación por burbujas?
R: El proceso de ordenación por burbujas consiste en comparar elementos adyacentes de una lista e intercambiarlos si están en el orden incorrecto.
P: ¿Qué se puede decir de la complejidad de la ordenación por burbujas?
R: La complejidad temporal de la ordenación por burbujas en el peor de los casos y en el caso medio es O(n^2), lo que significa que puede llevar mucho tiempo ordenar grandes conjuntos de datos.
Artículos relacionados
Autor
AlegsaOnline.com Ordenamiento por burbuja Leandro Alegsa
URL: https://es.alegsaonline.com/art/14976