Cómo funciona
Bubble Sort recorre el array comparando pares de elementos adyacentes. Si el elemento
de la izquierda es mayor que el de la derecha, los intercambia. Al terminar cada pasada completa,
el mayor elemento sin ordenar queda fijo al final: por eso la zona ordenada crece
de derecha a izquierda en la visualización.
Una optimización clave: si en una pasada entera no ocurre ningún intercambio, el array ya está
ordenado y el algoritmo termina antes de tiempo. Esto lo hace O(n) en el mejor caso
(array ya ordenado). Sin embargo, en el caso promedio y peor caso sigue siendo O(n²),
por lo que no se usa en producción para datos grandes.
Paso a paso con [5, 3, 8, 1]
- 01Pasada 1: compara 5 y 3 → 5 > 3, intercambia →
[3, 5, 8, 1]. Compara 5 y 8 → ok. Compara 8 y 1 → 8 > 1, intercambia → [3, 5, 1, 8]. El 8 queda fijo en su posición final.
- 02Pasada 2: compara 3 y 5 → ok. Compara 5 y 1 → 5 > 1, intercambia →
[3, 1, 5, 8]. El 5 queda fijo. Solo 2 comparaciones porque el último ya está ordenado.
- 03Pasada 3: compara 3 y 1 → 3 > 1, intercambia →
[1, 3, 5, 8]. El 3 queda fijo. Array completamente ordenado.
- ΣTotal: 3 pasadas, 6 comparaciones y 4 intercambios para n = 4. Bubble Sort hizo n·(n−1)/2 = 6 comparaciones, el máximo posible: no hubo salida anticipada porque la última pasada todavía intercambió.
Complejidad
- Mejor caso
- O(n)
- Caso promedio
- O(n²)
- Peor caso
- O(n²)
- Espacio extra
- O(1)
- Estable
- Sí
- In situ
- Sí