Ordenamiento de burbuja

El ordenamiento de burbuja es un algoritmo de ordenación basado en comparaciones que recorre repetidamente elementos adyacentes y los intercambia cuando están fuera del orden ascendente. Al terminar cada pasada completa, el valor más grande de la parte aún sin ordenar queda en su posición definitiva, en el extremo derecho. El nombre describe este desplazamiento repetido por la lista. Es fácil de seguir e implementar, pero su tiempo de ejecución cuadrático lo hace poco adecuado para colecciones grandes.

Algoritmo de ordenamiento de burbuja

Para un arreglo A con n elementos, compara A[0] con A[1], luego A[1] con A[2] y continúa por la parte sin ordenar. Cuando el valor de la izquierda es mayor que el de la derecha, intercámbialos. Esta condición produce un orden ascendente; invierte la comparación para ordenar de forma descendente.

Cada pasada recorre el arreglo de izquierda a derecha. Al terminar, el valor más grande de la parte recorrida queda en el límite derecho, así que la siguiente pasada puede detenerse una posición antes. La primera pasada abarca n - 1 pares, la siguiente n - 2, y así sucesivamente. Una implementación de pasadas fijas realiza n - 1 pasadas, aunque la última solo tiene un par que comprobar. Las listas con menos de dos elementos no requieren comparaciones.

Ejemplo del algoritmo de ordenamiento de burbuja

Considera la entrada (5, 3, 4, 2, 1). Durante la primera pasada, compara los pares adyacentes en orden: intercambia 5 y 3, y obtiene (3, 5, 4, 2, 1); intercambia 5 y 4, y obtiene (3, 4, 5, 2, 1); intercambia 5 y 2, y obtiene (3, 4, 2, 5, 1); por último, intercambia 5 y 1, y obtiene (3, 4, 2, 1, 5). El valor más grande ya quedó en su posición a la derecha.

La segunda pasada recorre solo los primeros cuatro valores y produce (3, 2, 1, 4, 5). La tercera modifica ese prefijo sin ordenar y lo deja como (2, 1, 3, 4, 5); la cuarta lo deja como (1, 2, 3, 4, 5). Este recorrido muestra por qué el límite se reduce después de cada pasada y por qué no se vuelven a comparar los valores que ya están en su posición definitiva.

Implementación del ordenamiento de burbuja en C++

Este programa completo ordena el ejemplo en el mismo vector. El límite del bucle interno n - i - 1 evita comparar el sufijo que ya quedó ordenado, mientras que values[j] > values[j + 1] intercambia un par adyacente fuera de orden y hace que los valores menores se desplacen hacia la izquierda.

Ejecuta este ejemplo:

El código y las etiquetas o salidas visibles de esta sección se mantienen en inglés.

#include <iostream>
#include <utility>
#include <vector>

void bubble_sort(std::vector<int>& values) {
    const int n = static_cast<int>(values.size());
    for (int i = 0; i < n - 1; ++i) {
        for (int j = 0; j < n - i - 1; ++j) {
            if (values[j] > values[j + 1]) {
                std::swap(values[j], values[j + 1]);
            }
        }
    }
}

int main() {
    std::vector<int> values{5, 3, 4, 2, 1};
    bubble_sort(values);
    std::cout << "Sorted:";
    for (int value : values) {
        std::cout << ' ' << value;
    }
    std::cout << '\n';
}

Sorted: 1 2 3 4 5

La ejecución proporcionada terminó correctamente y mostró los valores ordenados después de la etiqueta Sorted:, que permanece en inglés porque el bloque de código no se modifica.

Complejidad y limitaciones del ordenamiento de burbuja

La implementación de pasadas fijas realiza (n - 1) + (n - 2) + ... + 1, es decir, n(n - 1) / 2 comparaciones con cualquier orden de entrada. Por eso, sus complejidades temporales en el mejor, el promedio y el peor caso son todas O(n²). El peor caso, como una entrada ordenada de mayor a menor, también requiere muchos intercambios. La implementación modifica el vector directamente y solo utiliza un valor temporal para cada intercambio, por lo que su complejidad espacial auxiliar es O(1).

Una variante con salida anticipada puede registrar si hubo intercambios durante una pasada y detenerse cuando una pasada no modifica la lista. Esa variante tarda O(n) con una entrada ya ordenada; sus casos promedio y peor siguen siendo O(n²). El código de pasadas fijas mostrado arriba no incorpora esa optimización. El ordenamiento de burbuja resulta útil para aprender las comparaciones entre elementos adyacentes y para entradas muy pequeñas, pero los algoritmos de ordenación de la biblioteca estándar suelen ser más adecuados para colecciones grandes.