Ordenamiento Burbuja (Bubble Sort)

La idea detrás del Bubble Sort

Imagina que tienes una fila de personas ordenadas por estatura de forma aleatoria, y quieres ordenarlas de menor a mayor. Una forma simple: recorres la fila comparando cada persona con la que tiene al lado. Si están en el orden incorrecto, las intercambias. Repites esto hasta que toda la fila esté ordenada.

Los elementos más grandes "flotan" hacia el final, como burbujas que suben a la superficie del agua. De ahí el nombre.

El algoritmo paso a paso

Con el arreglo [5, 3, 8, 1, 2]:

Primera pasada (la burbuja más grande, 8, llega al final):

[5, 3, 8, 1, 2]  → Compara 5 y 3 → intercambia → [3, 5, 8, 1, 2]
[3, 5, 8, 1, 2]  → Compara 5 y 8 → OK          → [3, 5, 8, 1, 2]
[3, 5, 8, 1, 2]  → Compara 8 y 1 → intercambia → [3, 5, 1, 8, 2]
[3, 5, 1, 8, 2]  → Compara 8 y 2 → intercambia → [3, 5, 1, 2, 8] ✓

Segunda pasada (5 llega a su lugar):

[3, 5, 1, 2, 8]  → 3 y 5 → OK
[3, 5, 1, 2, 8]  → 5 y 1 → intercambia → [3, 1, 5, 2, 8]
[3, 1, 5, 2, 8]  → 5 y 2 → intercambia → [3, 1, 2, 5, 8] ✓

Tercera pasada (3 llega a su lugar):

[3, 1, 2, 5, 8]  → 3 y 1 → intercambia → [1, 3, 2, 5, 8]
[1, 3, 2, 5, 8]  → 3 y 2 → intercambia → [1, 2, 3, 5, 8] ✓

Cuarta pasada: No hay intercambios → ¡Ya está ordenado!

Implementación

void bubbleSort(vector<int> &v) {
    int n = v.size();

    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (v[j] > v[j + 1]) {
                swap(v[j], v[j + 1]);
            }
        }
    }
}

Línea por línea:

• for i = 0..n-2 → Necesitamos hasta n-1 pasadas.
• for j = 0..n-2-i → En cada pasada, no necesitamos revisar los últimos i elementos (ya están en su lugar).
• if (v[j] > v[j+1]) → Si el actual es mayor que el siguiente, están en desorden.
• swap(v[j], v[j+1]) → Intercambiar (la función swap viene con C++).

Optimización: detección temprana

Si en una pasada no se hizo ningún intercambio, el arreglo ya está ordenado:

void bubbleSortOptimizado(vector<int> &v) {
    int n = v.size();

    for (int i = 0; i < n - 1; i++) {
        bool huboIntercambio = false;

        for (int j = 0; j < n - 1 - i; j++) {
            if (v[j] > v[j + 1]) {
                swap(v[j], v[j + 1]);
                huboIntercambio = true;
            }
        }

        if (!huboIntercambio) break;  // Ya está ordenado
    }
}

Complejidad

• Peor caso (arreglo al revés): $O(n^2)$ comparaciones e intercambios.
• Mejor caso (ya ordenado, con optimización): $O(n)$ comparaciones, 0 intercambios.
• Caso promedio: $O(n^2)$.

Para $n = 10,000$, hace hasta 100 millones de operaciones. Para $n = 100,000$, serían 10 mil millones: ¡demasiado lento!

Contar inversiones

Una inversión es un par (i, j) donde i < j pero arr[i] > arr[j]. Bubble Sort hace exactamente un swap por cada inversión, así que el número de swaps de Bubble Sort = número de inversiones.

long long contarInversiones(vector<int> v) {
    long long inversiones = 0;
    int n = v.size();
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (v[j] > v[j + 1]) {
                swap(v[j], v[j + 1]);
                inversiones++;
            }
        }
    }
    return inversiones;
}

Ejercicio de práctica

Implementa Bubble Sort y muestra el estado del arreglo después de cada pasada completa.

Entrada:

5
4 2 5 1 3

Salida:

2 4 1 3 5
2 1 3 4 5
1 2 3 4 5
1 2 3 4 5

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> v(n);
    for (int i = 0; i < n; i++) cin >> v[i];

    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (v[j] > v[j + 1]) {
                swap(v[j], v[j + 1]);
            }
        }
        // Imprimir estado después de la pasada
        for (int k = 0; k < n; k++) {
            if (k > 0) cout << " ";
            cout << v[k];
        }
        cout << endl;
    }

    return 0;
}

Siguiente paso

Aprende el Ordenamiento por Cubeta (Counting Sort), un algoritmo que puede ordenar en tiempo lineal.