15/07/2010
El ordenamiento de burbuja, conocido en inglés como Bubble Sort, es uno de los algoritmos de ordenación más simples y fundamentales en el mundo de la programación. Aunque no es el más eficiente para grandes volúmenes de datos, su lógica sencilla lo convierte en una excelente herramienta educativa para quienes se inician en el estudio de estructuras de datos y algoritmos. Su nombre proviene de la forma en que los elementos más grandes "burbujean" hacia el final de la lista, de manera similar a como las burbujas de aire suben a la superficie del agua.
Este artículo te guiará a través de todo lo que necesitas saber sobre el Bubble Sort: su funcionamiento interno, cómo implementarlo en distintos lenguajes, sus variantes optimizadas, su análisis de complejidad y sus aplicaciones prácticas. Al final, tendrás una comprensión sólida de este clásico algoritmo.
¿Cómo Funciona el Algoritmo Bubble Sort?
La idea central del Bubble Sort es recorrer repetidamente una lista, comparando cada par de elementos adyacentes y cambiándolos de posición si están en el orden incorrecto. Este proceso se repite hasta que no se necesiten más intercambios, lo que indica que la lista está completamente ordenada.
El proceso se puede desglosar en los siguientes pasos:
- Primera Iteración (Pasada): Se comienza desde el primer índice del arreglo. Se compara el primer elemento con el segundo. Si el primero es mayor que el segundo (en un ordenamiento ascendente), se intercambian. Luego, se compara el segundo con el tercero, el tercero con el cuarto, y así sucesivamente hasta el final del arreglo. Al concluir esta primera pasada, el elemento más grande de toda la lista estará garantizado en la última posición.
- Iteraciones Restantes: El proceso se repite, pero en cada nueva pasada, se excluye el último elemento ya ordenado. Es decir, en la segunda pasada, el recorrido se hace hasta el penúltimo elemento, colocando el segundo más grande en su posición correcta. Esto continúa hasta que todos los elementos estén en su lugar.
Un Ejemplo Práctico
Imaginemos que queremos ordenar el siguiente arreglo de números en orden ascendente: [5, 3, 8, 4, 6].
Primera Pasada:
- Comparamos 5 y 3. Como 5 > 3, los intercambiamos:
[3, 5, 8, 4, 6] - Comparamos 5 y 8. Como 5 < 8, no hacemos nada:
[3, 5, 8, 4, 6] - Comparamos 8 y 4. Como 8 > 4, los intercambiamos:
[3, 5, 4, 8, 6] - Comparamos 8 y 6. Como 8 > 6, los intercambiamos:
[3, 5, 4, 6, 8]
Al final de la primera pasada, el número más grande (8) está en su posición final.
Segunda Pasada:
- Comparamos 3 y 5. Como 3 < 5, no hacemos nada:
[3, 5, 4, 6, 8] - Comparamos 5 y 4. Como 5 > 4, los intercambiamos:
[3, 4, 5, 6, 8] - Comparamos 5 y 6. Como 5 < 6, no hacemos nada:
[3, 4, 5, 6, 8]
El arreglo ya está ordenado, pero el algoritmo aún no lo sabe. Continuaría con las siguientes pasadas hasta confirmar que no se necesitan más intercambios.
Implementación en Diferentes Lenguajes
La lógica del Bubble Sort es universal, lo que facilita su implementación en cualquier lenguaje de programación. A continuación, se muestran ejemplos en Python, Java y C++.
Bubble Sort en Python
def bubbleSort(array): n = len(array) # Recorrer todos los elementos del arreglo for i in range(n): # El último i elementos ya están en su lugar for j in range(0, n - i - 1): # Recorrer el arreglo de 0 a n-i-1 # Intercambiar si el elemento encontrado es mayor # que el siguiente elemento if array[j] > array[j + 1]: array[j], array[j + 1] = array[j + 1], array[j] data = [-2, 45, 0, 11, -9] bubbleSort(data) print('Arreglo Ordenado en Orden Ascendente:') print(data)Bubble Sort en Java
import java.util.Arrays; class Main { static void bubbleSort(int array[]) { int size = array.length; // Bucle para acceder a cada elemento del arreglo for (int i = 0; i < size - 1; i++) // Bucle para comparar elementos del arreglo for (int j = 0; j < size - i - 1; j++) // Comparar dos elementos adyacentes if (array[j] > array[j + 1]) { // El intercambio ocurre si los elementos no están en el orden deseado int temp = array[j]; array[j] = array[j + 1]; array[j + 1] = temp; } } public static void main(String args[]) { int[] data = { -2, 45, 0, 11, -9 }; Main.bubbleSort(data); System.out.println("Arreglo Ordenado en Orden Ascendente:"); System.out.println(Arrays.toString(data)); } }Bubble Sort en C++
#include <iostream> using namespace std; void bubbleSort(int array[], int size) { for (int step = 0; step < size - 1; ++step) { for (int i = 0; i < size - step - 1; ++i) { if (array[i] > array[i + 1]) { int temp = array[i]; array[i] = array[i + 1]; array[i + 1] = temp; } } } } int main() { int data[] = {-2, 45, 0, 11, -9}; int size = sizeof(data) / sizeof(data[0]); bubbleSort(data, size); cout << "Arreglo Ordenado en Orden Ascendente:\n"; for (int i = 0; i < size; ++i) { cout << " " << data[i]; } cout << "\n"; }Optimizando el Bubble Sort
Una de las mayores críticas al Bubble Sort es que realiza todas las comparaciones incluso si el arreglo ya está ordenado. Esto aumenta innecesariamente el tiempo de ejecución. Para solucionar esto, podemos introducir una variable booleana (una "bandera" o flag) que verifique si se realizó algún intercambio en una pasada.
La lógica de la optimización es simple: si después de una pasada completa por el arreglo no se ha realizado ningún intercambio, significa que el arreglo ya está ordenado y podemos detener el algoritmo prematuramente.
Algoritmo de Bubble Sort Optimizado
bubbleSortOptimizado(array) para i desde 0 hasta tamañoDeArray - 1 intercambiado = falso para j desde 0 hasta tamañoDeArray - 1 - i si elementoIzquierdo > elementoDerecho intercambiar(elementoIzquierdo, elementoDerecho) intercambiado = verdadero si intercambiado == falso romper // Salir del bucle principal fin bubbleSortOptimizadoEsta pequeña mejora cambia drásticamente el rendimiento en el mejor de los casos, cuando el arreglo ya está ordenado, sin afectar el peor de los casos.
Análisis de Complejidad
La complejidad de un algoritmo es una medida de cuántos recursos (tiempo y espacio) consume. Para el Bubble Sort, el análisis es el siguiente:
Complejidad Temporal (Time Complexity)
La complejidad temporal se mide en función del número de comparaciones. Debido a sus dos bucles anidados, donde el bucle interno depende del externo, el número de operaciones es proporcional a n², donde 'n' es el número de elementos.
| Caso | Complejidad | Descripción |
|---|---|---|
| Peor Caso | O(n²) | Ocurre cuando el arreglo está ordenado en orden inverso. Se necesita el máximo número de intercambios. |
| Caso Promedio | O(n²) | Ocurre cuando los elementos del arreglo están en un orden aleatorio. |
| Mejor Caso | O(n) | Ocurre cuando el arreglo ya está ordenado. Con la versión optimizada, solo se necesita una pasada para confirmarlo. |
Complejidad Espacial (Space Complexity)
La complejidad espacial del Bubble Sort es O(1). Esto significa que ordena la lista "in-place" (en el mismo lugar), sin necesidad de crear estructuras de datos adicionales. Solo requiere una variable temporal para realizar los intercambios, por lo que la memoria utilizada no depende del tamaño de la entrada.
Bubble Sort Recursivo
Aunque comúnmente se implementa de forma iterativa, el Bubble Sort también puede expresarse de forma recursiva. La idea es realizar una pasada para colocar el elemento más grande al final y luego llamar recursivamente a la función para el resto del arreglo (de tamaño n-1).
- Caso Base: Si el tamaño del arreglo es 1, ya está ordenado, por lo que la función retorna.
- Paso Recursivo: Se realiza una pasada completa sobre los elementos. Después de la pasada, el elemento más grande está en su lugar. Luego, se llama a la función para el sub-arreglo que excluye al último elemento.
Preguntas Frecuentes (FAQ)
¿Es el algoritmo Bubble Sort estable?
Sí, el Bubble Sort es un algoritmo de ordenamiento estable. Un algoritmo es estable si dos elementos con valores iguales mantienen su orden relativo original en la salida ordenada. Dado que el Bubble Sort solo intercambia elementos si el primero es estrictamente mayor que el segundo, el orden de los elementos iguales nunca se altera.
¿Por qué el Bubble Sort es ineficiente?
Su ineficiencia se debe a su complejidad temporal de O(n²). Esto significa que el tiempo de ejecución crece cuadráticamente con el número de elementos. Si duplicas el tamaño de la lista, el tiempo para ordenarla se cuadruplica. Esto lo hace impráctico para conjuntos de datos grandes, donde algoritmos como Merge Sort o Quick Sort (con complejidad promedio de O(n log n)) son mucho más rápidos.
¿Cuándo es útil usar Bubble Sort?
A pesar de su ineficiencia, el Bubble Sort tiene su lugar:
- Propósitos Educativos: Es ideal para enseñar los conceptos básicos de los algoritmos de ordenamiento debido a su simplicidad.
- Pequeños Conjuntos de Datos: Para listas muy pequeñas, la diferencia de rendimiento con algoritmos más complejos es insignificante, y su fácil implementación puede ser una ventaja.
- Verificación de Ordenamiento: La versión optimizada es muy eficiente para verificar si una lista ya está ordenada.
En resumen, el Bubble Sort es una pieza fundamental en la historia de la informática. Aunque raramente es la mejor opción para aplicaciones de producción, comprender su funcionamiento proporciona una base sólida para abordar algoritmos más complejos y eficientes.
Si quieres conocer otros artículos parecidos a Bubble Sort: Guía Completa del Algoritmo puedes visitar la categoría Juegos.