Bubble Sort — Guia · Computation Lab

Que es y por que importa

Bubble Sort es el algoritmo de ordenamiento mas intuitivo: compara elementos vecinos y los intercambia si estan en orden incorrecto. Es ineficiente para listas grandes, pero revela algo profundo: el orden global puede emerger de decisiones puramente locales.

Comparacion local Intercambios adyacentes O(n²) tiempo Estable In-place

Idea central: El algoritmo no "ve" el array completo. Solo conoce dos elementos a la vez. Aun asi, el orden emerge. Este patron — reglas locales produciendo orden global — aparece en fisica, biologia y economia.

Pseudocodigo

for i in 0..n-1:
  swapped = false
  for j in 0..n-i-2:
    if A[j] > A[j+1]:
      swap(A[j], A[j+1])
      swapped = true
  if not swapped:
    break  # ya ordenado

La optimizacion swapped permite terminar temprano si una pasada no hace intercambios.

Estados visuales

Sin procesar

Comparando

Intercambiando

Ordenado

La intuicion: burbujas flotando

Imagina burbujas de aire en agua. Las mas grandes suben mas rapido. En Bubble Sort, los elementos "grandes" flotan hacia el final del array, uno por pasada.

Pasada 1: El mayor llega al final
Pasada 2: El segundo mayor llega a su posicion
Pasada n-1: Todo ordenado

La zona verde (ordenada) crece desde la derecha. Observa como el "frente de ordenamiento" avanza.

Complejidad: el precio del orden

Peor caso (inverso)O(n²)

Mejor caso (ordenado)O(n)

Caso promedioO(n²)

Espacio extraO(1)

En numeros:
n = 10 → ~45 comparaciones
n = 100 → ~5,000 comparaciones
n = 1000 → ~500,000 comparaciones

Experimentos guiados

Tres formas de entender Bubble Sort

Experimento 1: Peor caso vs mejor caso

Genera un array ordenado inversamente (peor caso)
Ejecuta y anota: comparaciones, swaps, pasadas
Resetea y genera un array ya ordenado (mejor caso)
Ejecuta y compara los contadores

Hipotesis: El array ordenado deberia terminar en 1 pasada (con la optimizacion de early exit).

Observa: En el peor caso, cada elemento debe "burbujear" toda la distancia hasta su posicion final.

Experimento 2: El efecto de duplicar n

Usa n = 10, genera array aleatorio, ejecuta
Anota las comparaciones totales
Repite con n = 20
Calcula la proporcion: comparaciones(20) / comparaciones(10)

Hipotesis: Si O(n²), duplicar n deberia cuadruplicar (~4x) las comparaciones.

El crecimiento cuadratico es brutal

Experimento 3: El array "casi ordenado"

Genera un array ordenado
Intercambia manualmente 2-3 elementos adyacentes
Ejecuta Bubble Sort
Compara con el peor caso del mismo tamano

Observa: Bubble Sort es sorprendentemente eficiente cuando el array esta "casi" ordenado. Pocas pasadas, pocos swaps.

Caso favorable real

▶ Ir a la simulacion

Conexiones interdisciplinarias

El mismo patron en otros sistemas

La idea de "reglas locales → orden global" aparece en muchos sistemas naturales y artificiales. Bubble Sort es un ejemplo computacional de emergencia.

🧬

Seleccion Natural Cada organismo compite localmente. No hay "planificador" global. Aun asi, las especies se adaptan. El fitness "burbujea" hacia arriba generacion tras generacion.

🎮

Game of Life Cada celda solo mira a sus 8 vecinas. Reglas triviales. Pero emergen naves espaciales, osciladores, incluso maquinas de Turing. Orden desde el caos local.

⚗️

Equilibrio Quimico Las moleculas no "saben" hacia donde va la reaccion. Solo colisionan localmente. El equilibrio emerge de billones de interacciones aleatorias.

🌡️

Termodinamica Las moleculas de un gas intercambian energia en colisiones locales. La distribucion de Maxwell-Boltzmann emerge — un "orden estadistico" sin coordinador central.

Por que estudiar un algoritmo "malo"?

Bubble Sort casi nunca se usa en produccion. Entonces, por que aprenderlo?

Pedagogico: Es el algoritmo mas facil de entender y visualizar
Baseline: Sirve como referencia para comparar con algoritmos mejores
Conceptual: Ilustra la diferencia entre O(n) y O(n²) de forma visceral
Emergencia: Demuestra que el orden puede emerger de reglas locales

Cuando SI usar Bubble Sort

Arrays muy pequenos (n < 10): El overhead de algoritmos complejos no vale la pena
Arrays casi ordenados: O(n) en el mejor caso
Memoria limitada: Es in-place, O(1) espacio extra
Estabilidad requerida: No cambia el orden de elementos iguales

En la practica, Insertion Sort es mejor para arrays pequenos/casi-ordenados. Para arrays grandes: Merge Sort, Quick Sort, o Timsort.

Limitaciones del modelo

Que NO muestra esta simulacion

Cache performance: En CPUs reales, el acceso secuencial de Bubble Sort es cache-friendly, pero esto no compensa su O(n²)
Comparacion con otros: La simulacion muestra solo Bubble Sort; idealmente compararias con Quick Sort lado a lado

Escalas reales: Con n = 20, no sientes la diferencia entre O(n) y O(n²). Con n = 10,000, la diferencia es brutal
Variantes: Existen optimizaciones (Cocktail Sort, Comb Sort) que no se muestran aqui

Preguntas para reflexionar

Por que el algoritmo se llama "Bubble" Sort? Que "flota" hacia donde?
Si el array tiene n elementos, cual es el maximo numero de pasadas necesarias? Por que?
Por que Bubble Sort es estable? Que condicion en el codigo garantiza esto?
Si tuvieras que ordenar 1 millon de numeros, cuanto tiempo tomaria Bubble Sort comparado con un algoritmo O(n log n)?
En que otros sistemas naturales ves "orden emergente de reglas locales"?

En resumen

Bubble Sort como metafora

Bubble Sort es mas que un algoritmo ineficiente. Es una demostracion de que el orden puede emerger sin un controlador central. Cada comparacion es local, miope, sin vision del array completo. Y aun asi, el sistema converge al orden total.

Este patron — emergencia, auto-organizacion, orden desde el caos — es uno de los temas mas profundos de la ciencia. Lo veras en fisica estadistica, biologia evolutiva, economia de mercados, y redes neuronales.

Bubble Sort es lento, pero es sabio.