Overview
Bubble Sort compara elementos adyacentes y hace swap cuando están fuera de orden. En cada pasada, el mayor elemento pendiente termina al final.
Analogy
Como burbujas en agua: las más grandes suben a la superficie en cada ronda.
Step-by-step
- Recorre la lista y compara arr[j] con arr[j+1].
- Si arr[j] > arr[j+1], realiza swap.
- Después de una pasada, el mayor elemento queda fijo al final.
- Reduce el rango de la siguiente pasada porque el final ya está sorted.
- Si no hubo swaps, termina temprano.
Visual
Pasada 1: [5,3,8,1,2] -> [3,5,1,2,8]; luego se recorta el rango en cada pasada.
Common mistakes
- No reducir el límite del inner loop.
- Usar >= en lugar de > y perder estabilidad.
- No aplicar early exit cuando una pasada tiene 0 swaps.
Practice questions
- Traza Bubble Sort en una lista ya ordenada con y sin early exit.
- Explica por qué Bubble Sort es estable.
- Adáptalo para ordenar de mayor a menor.
Time
O(n²) peor/promedio, O(n) mejor caso con early exit