Bubble sort (ordenamiento de burbuja): cómo funciona, código y complejidad

La idea en palabras sencillas

Compara los dos primeros elementos. Si el primero es mayor, intercámbialos. Luego compara el segundo y el tercero, después el tercero y el cuarto, y así hasta el final de la lista. Esto es una pasada. Tras la primera pasada, el mayor elemento queda garantizado en la última posición, porque cada comparación lo desplazó un paso a la derecha.

Repite la pasada sobre la parte sin ordenar, que se reduce en un elemento cada vez. Si una pasada completa no hace ningún intercambio, la lista está ordenada y puedes detenerte antes.

Ejemplo resuelto, pasada a pasada

Ordena [5, 1, 4, 2, 8] de forma ascendente. Los elementos situados después de la barra ya están en su posición final.

Sin la salida anticipada, el algoritmo haría una cuarta pasada. Con ella, aquí bastan tres pasadas.

Implementación en Python

def bubble_sort(items):
    """Sort a list in place, ascending. Returns the same list."""
    n = len(items)
    for end in range(n - 1, 0, -1):     # last index of the unsorted part
        swapped = False
        for i in range(end):
            if items[i] > items[i + 1]:  # strict >, keeps equal items in order
                items[i], items[i + 1] = items[i + 1], items[i]
                swapped = True
        if not swapped:                  # no swaps: already sorted
            break
    return items
print(bubble_sort([5, 1, 4, 2, 8]))     # [1, 2, 4, 5, 8]
print(bubble_sort([3, 3, 1]))           # [1, 3, 3]
print(bubble_sort([]))                  # []

El bucle interno se detiene en end porque todo lo que hay después ya está en su sitio. La bandera swapped da el mejor caso O(n) con una entrada ordenada.

Complejidad temporal y espacial

Con 10.000 elementos en orden inverso, son casi 50 millones de comparaciones e intercambios. El número de intercambios siempre es igual al número de inversiones, que son los pares de elementos desordenados entre sí.

Cómo se compara bubble sort con otros ordenamientos

Bubble sort es estable porque solo intercambia elementos adyacentes y solo cuando están estrictamente desordenados, así que los elementos iguales nunca se adelantan entre sí. Insertion sort tiene la misma complejidad y estabilidad, pero en la práctica hace menos escrituras y es más rápido, por lo que se usa él, y no bubble sort, dentro de algoritmos híbridos como Timsort.

Variantes y errores comunes

• Cocktail shaker sort recorre la lista de izquierda a derecha y luego de derecha a izquierda en pasadas alternas, lo que lleva más rápido al principio los elementos pequeños que están al final (llamados tortugas). Sigue siendo O(n²).
• Comb sort compara elementos separados por un hueco y va reduciendo ese hueco, lo que elimina muchas tortugas pronto; con hueco 1 se convierte en bubble sort.
• Odd-even transposition sort compara todos los pares impares y luego todos los pares pares, y se usa para enseñar ordenamiento en paralelo.

Cuándo usar bubble sort

Casi nunca en código de producción. En Python, llama a sorted(items) o items.sort(), que usan Timsort, se ejecutan en O(n log n) y son estables. Aun así, conviene conocer bubble sort porque es el ordenamiento más fácil de explicar, su demostración de corrección es sencilla de seguir y es una primera pregunta habitual de entrevistas y exámenes sobre bucles, intercambios y complejidad.

La única ventaja práctica es detectar una lista ordenada en una sola pasada O(n), pero un simple bucle que compare vecinos lo hace sin ordenar nada.