Ordenamiento de burbuja
La ordenación por burbujas es un algoritmo de ordenación sencillo. Es fácil de entender, por lo que se suele enseñar a los nuevos estudiantes. No es tan eficiente como otros algoritmos de ordenación.
El nombre de la clasificación por burbujas proviene del hecho de que cada elemento de la lista "burbujea" hasta donde debe ir, como las burbujas en el agua.
Una clase de burbuja ilustrada
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²).
Un ejemplo de ordenación de burbujas. Empezando por el principio de la lista, compara el siguiente par. Intercambia sus posiciones si no están en el orden correcto (el segundo del par es más pequeño que el primero del par). Después de cada iteración, es necesario comparar un elemento menos (el último) hasta que no queden elementos por comparar.
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.
