3 - Bubble Sort

Bubble Sort es el algoritmo de ordenamiento más conocido y uno de los más sencillos de implementar en Python. Su mecánica se basa en recorrer la lista varias veces, comparando pares adyacentes y haciendo que el elemento más grande "burbujee" hacia el final en cada pasada.

3.1 Idea general del algoritmo

El algoritmo realiza pasadas sucesivas sobre la lista. En cada pasada, examina cada par adyacente y los intercambia si están fuera de orden. Al finalizar la primera pasada, el elemento más grande queda al final; en la segunda, el segundo más grande queda en la penúltima posición, y así sucesivamente.

3.2 Comparación de elementos adyacentes

El recorrido interno compara valores[j] con valores[j + 1]. Si el orden deseado es ascendente y valores[j] > valores[j + 1], se produce un intercambio.

3.3 Intercambio (swap) cuando es necesario

El intercambio se realiza con la función swap definida previamente:

def swap(valores, i, j):
  valores[i], valores[j] = valores[j], valores[i]

Centralizar esta operación evita duplicar código y reduce errores.

3.4 Burbujeo del mayor al final

Cada pasada garantiza que el mayor de la porción revisada termina al final de la sección considerada. Por eso el límite interno puede reducirse en cada iteración externa: no es necesario volver a tocar las posiciones ya ordenadas al final de la lista.

3.5 Optimización: cortar si no hubo swaps

Si en una pasada completa no se realiza ningún intercambio, la lista ya está ordenada y el algoritmo puede detenerse. Esto mejora mucho el rendimiento en listas casi ordenadas.

3.6 Implementación paso a paso en Python

Versión clásica con corte temprano; se asume que swap ya está declarada.

def bubble_sort(valores):
  n = len(valores)
  for i in range(n - 1):
    hubo_intercambio = False
    limite = n - 1 - i  # el último ya quedó en su lugar
    for j in range(limite):
      if valores[j] > valores[j + 1]:
        swap(valores, j, j + 1)
        hubo_intercambio = True
    if not hubo_intercambio:
      break  # la lista ya está ordenada

Explicación línea por línea:

• for i in range(n - 1): controla las pasadas; tras cada pasada, el mayor de la sección queda al final.
• hubo_intercambio = False: flag para saber si en esta pasada hubo cambios.
• limite = n - 1 - i: evita comparar posiciones finales ya ordenadas.
• for j in range(limite): recorre pares adyacentes dentro del rango vigente.
• if valores[j] > valores[j + 1]: detecta si el par está desordenado para el orden ascendente.
• swap(valores, j, j + 1): intercambia los elementos fuera de orden.
• hubo_intercambio = True: marca que hubo al menos un swap en esta pasada.
• if not hubo_intercambio: break: si no hubo swaps, la lista ya estaba ordenada y se corta el algoritmo.

3.7 Complejidad temporal y espacial

• Tiempo: O(n^2) en promedio y peor caso (listas inversas); O(n) en el mejor caso si el corte temprano detecta una lista ya ordenada.
• Memoria: O(1) espacio adicional; trabaja in-place.
• Estabilidad: es estable, no cambia el orden relativo de elementos iguales.

3.8 Ventajas y desventajas

• Ventajas: implementación muy simple; estable; fácil de depurar paso a paso; buen rendimiento si la lista ya está casi ordenada gracias al corte temprano.
• Desventajas: rendimiento pobre en listas medianas o grandes; su complejidad cuadrática lo hace inviable para grandes volúmenes de datos.

3.9 Casos ideales y peores casos

• Ideal: listas pequeñas o casi ordenadas donde el corte temprano termina rápido.
• Peor caso: lista ordenada en sentido inverso; requiere la máxima cantidad de comparaciones e intercambios.

Bubble Sort sigue siendo valioso para docencia y para validar otros algoritmos: su simplicidad permite comparar resultados y detectar errores en implementaciones más complejas.

3.10 Archivo único de trabajo

Siguiendo el mismo enfoque del tema anterior, vamos a usar un solo archivo para probar el algoritmo con datos de ejemplo. Esto permite copiar, ejecutar y revisar el resultado rápidamente.

def swap(valores, i, j):
  valores[i], valores[j] = valores[j], valores[i]

def imprimir_lista(valores):
  for valor in valores:
    print(valor, end=", ")

def bubble_sort(valores):
  n = len(valores)
  for i in range(n - 1):
    hubo_intercambio = False
    limite = n - 1 - i
    for j in range(limite):
      if valores[j] > valores[j + 1]:
        swap(valores, j, j + 1)
        hubo_intercambio = True
    if not hubo_intercambio:
      break

datos = [5, 2, 9, 1, 3]
print("Antes: ", end="")
imprimir_lista(datos)
print()

bubble_sort(datos)

print("Despues: ", end="")
imprimir_lista(datos)
print()