Ordenamiento Burbuja (Bubble Sort)

¿Qué es Bubble Sort?

El ordenamiento burbuja es un algoritmo simple que compara elementos adyacentes y los intercambia si están en el orden incorrecto. Los elementos más grandes "burbujean" hacia el final.

Idea básica

1. Recorrer el arreglo comparando pares adyacentes
2. Si están desordenados, intercambiarlos
3. Repetir hasta que no haya intercambios

Visualización

Arreglo inicial: [5, 3, 8, 4, 2]

Primera pasada:
[5, 3, 8, 4, 2] → [3, 5, 8, 4, 2]  (5 > 3, intercambiar)
[3, 5, 8, 4, 2] → [3, 5, 8, 4, 2]  (5 < 8, no cambiar)
[3, 5, 8, 4, 2] → [3, 5, 4, 8, 2]  (8 > 4, intercambiar)
[3, 5, 4, 8, 2] → [3, 5, 4, 2, 8]  (8 > 2, intercambiar)
                                    ↑ 8 llegó al final

Segunda pasada:
[3, 5, 4, 2, 8] → [3, 5, 4, 2, 8]  (3 < 5, no cambiar)
[3, 5, 4, 2, 8] → [3, 4, 5, 2, 8]  (5 > 4, intercambiar)
[3, 4, 5, 2, 8] → [3, 4, 2, 5, 8]  (5 > 2, intercambiar)
                                    ↑ 5 llegó a su lugar

Y así sucesivamente...

Implementación básica

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

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

Implementación optimizada

Termina temprano si no hay intercambios:

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

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

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

        // Si no hubo intercambios, el arreglo ya está ordenado
        if (!huboIntercambio) break;
    }
}

Análisis de complejidad

Espacio: $O(1)$ - ordenamiento in-place.

¿Por qué O(n²)?

n-1 comparaciones en pasada 1
n-2 comparaciones en pasada 2
...
1 comparación en pasada n-1

Total = (n-1) + (n-2) + ... + 1 = n(n-1)/2 = O(n²)

Conteo de intercambios

El número de intercambios en Bubble Sort es igual al número de inversiones en el arreglo:

int contarIntercambios(vector<int> arr) {
    int n = arr.size();
    int intercambios = 0;

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

    return intercambios;
}

Ventajas

• ✅ Muy simple de entender e implementar
• ✅ Estable (mantiene orden relativo de iguales)
• ✅ In-place (no necesita memoria extra)
• ✅ Detecta si el arreglo ya está ordenado (versión optimizada)

Desventajas

• ❌ Muy lento para arreglos grandes
• ❌ $O(n^2)$ es prohibitivo para n > 10,000

Cuándo usar Bubble Sort

• Fines educativos
• Arreglos muy pequeños (< 20 elementos)
• Cuando necesitas contar inversiones
• En competencias: Casi nunca, usa sort() de la STL

Variantes

Ordenar de mayor a menor

void bubbleSortDescendente(vector<int>& arr) {
    int n = arr.size();

    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] < arr[j + 1]) {  // Cambio de signo
                swap(arr[j], arr[j + 1]);
            }
        }
    }
}

Cocktail Sort (Bubble Sort bidireccional)

Alterna pasadas hacia adelante y hacia atrás:

void cocktailSort(vector<int>& arr) {
    int n = arr.size();
    bool intercambio = true;
    int inicio = 0, fin = n - 1;

    while (intercambio) {
        intercambio = false;

        // Izquierda a derecha
        for (int i = inicio; i < fin; i++) {
            if (arr[i] > arr[i + 1]) {
                swap(arr[i], arr[i + 1]);
                intercambio = true;
            }
        }
        fin--;

        if (!intercambio) break;
        intercambio = false;

        // Derecha a izquierda
        for (int i = fin; i > inicio; i--) {
            if (arr[i] < arr[i - 1]) {
                swap(arr[i], arr[i - 1]);
                intercambio = true;
            }
        }
        inicio++;
    }
}

Ejercicios de práctica

Ejercicio 1

Modifica Bubble Sort para que ordene strings alfabéticamente.

void bubbleSortStrings(vector<string>& arr) {
    int n = arr.size();

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

Ejercicio 2

Encuentra el k-ésimo elemento más pequeño usando una variante de Bubble Sort (hacer solo k pasadas).

int kEsimoMenor(vector<int> arr, int k) {
    int n = arr.size();

    // Solo k pasadas desde el final hacia atrás
    for (int i = 0; i < k; i++) {
        for (int j = n - 1; j > i; j--) {
            if (arr[j] < arr[j - 1]) {
                swap(arr[j], arr[j - 1]);
            }
        }
    }

    return arr[k - 1];
}

Siguiente paso

Aprende sobre Ordenamiento por Cubeta para casos especiales donde puedes ordenar en O(n).