Ordenamiento de burbuja

5.1 Definición del ordenamiento de burbuja

Ordenamiento de burbuja (Bubble Sort) es un algoritmo de ordenamiento sencillo que pasa repetidamente a través de una lista, comparando elementos adyacentes y cambiándolos de lugar si están en el orden incorrecto. Este proceso continúa hasta que la lista esté completamente ordenada.

Principio de funcionamiento:

1. El algoritmo pasa por la lista y compara cada par de elementos adyacentes.
2. Si los elementos están en el orden incorrecto (el primero es mayor que el segundo para orden ascendente) — se intercambian.
3. Este proceso se repite para todos los pares de elementos en la lista.
4. Después de cada pasada completa, el mayor elemento "sube" a su lugar (como una burbuja en la superficie del agua), por lo que ya no participa en las siguientes pasadas.
5. El proceso se repite hasta que la lista esté ordenada.

Complejidad temporal y espacial del ordenamiento de burbuja

Complejidad temporal:

• En el peor caso: O(n^2) — ocurre cuando los elementos están inicialmente ordenados en orden inverso.
• En el caso promedio: O(n^2) — ocurre para una disposición aleatoria de elementos.
• En el mejor caso: O(n) — ocurre cuando los elementos ya están ordenados (el algoritmo puede optimizarse para este caso agregando una verificación de si ocurrió un intercambio de elementos en la pasada).

Complejidad espacial:

O(1) — ya que el algoritmo usa una cantidad constante de memoria adicional (solo unas pocas variables para almacenar valores temporales).

5.2 Implementación del algoritmo

El algoritmo de "ordenamiento de burbuja" es el algoritmo más sencillo y primitivo para ordenar una lista/arreglo de elementos. Simplemente compara pares de elementos y los intercambia si es necesario.

Versión 1:

array = [6, 43, 2, 1, 2, 1, 1, 1, 1, 6, 7, 8]
n = len(array)
            
for i in range(n):
    for j in range(n - 1):
        if array[j] > array[j + 1]:
            array[j], array[j + 1] = array[j + 1], array[j]  # Intercambio de elementos

print("Arreglo ordenado:", array)
# Salida: Arreglo ordenado: [1, 1, 1, 1, 1, 2, 2, 6, 6, 7, 8, 43]

El ciclo interno (destacado en verde) compara el elemento con su vecino de la derecha. Y si es necesario, intercambia los elementos.

Versión 2:

En nuestro algoritmo podemos añadir inmediatamente una optimización: después de la primera pasada del algoritmo, el mayor elemento estará al extremo derecho, por lo que ya no necesitas considerarlo en el siguiente ciclo.

Después de la segunda iteración, habrá 2 elementos máximos a la derecha, por lo que el ciclo interno puede ir hasta n - 1 - i en lugar de n - 1. Donde i es la cantidad de iteraciones realizadas por el ciclo externo.

La nueva versión se verá así:

array = [6, 43, 2, 1, 2, 1, 1, 1, 1, 6, 7, 8]
n = len(array)
            
for i in range(n):
    for j in range(n - 1 - i):
        if array[j] > array[j + 1]:
            array[j], array[j + 1] = array[j + 1], array[j]  # Intercambio de elementos

print("Arreglo ordenado:", array)
# Salida: Arreglo ordenado: [1, 1, 1, 1, 1, 2, 2, 6, 6, 7, 8, 43]

Versión 3:

Además, el arreglo ya puede estar casi ordenado. Por lo tanto, se puede añadir una optimización: si el ciclo interno ha pasado por todos los elementos pero no realizó ningún intercambio, entonces la ordenación ha terminado.

En esta versión se utiliza la variable swapped, que rastrea si ha habido un intercambio de elementos durante la última pasada. Si después de recorrer el arreglo no ha habido ningún intercambio, esto significa que el arreglo ya está ordenado, y realizar más iteraciones es inútil porque no mejorarán la ordenación. Así, la variable swapped permite acelerar significativamente el algoritmo en arreglos casi ordenados, terminando su ejecución anticipadamente.

Implementación del ordenamiento de burbuja en Python:

def bubble_sort(array):
    n = len(array)
    for i in range(n):
        swapped = False  # Optimización: verifica si ocurrió un intercambio
        for j in range(0, n - i - 1):
            if array[j] > array[j + 1]:
                array[j], array[j + 1] = array[j + 1], array[j]  # Intercambio de elementos
                swapped = True
        if not swapped:
            break  # Si no hubo intercambios, el arreglo ya está ordenado
    return array

# Ejemplo de uso:
array = [64, 34, 25, 12, 22, 11, 90]
sorted_array = bubble_sort(array)
print("Arreglo ordenado:", sorted_array)
# Salida: Arreglo ordenado: [11, 12, 22, 25, 34, 64, 90]