Overview
Bubble Sort compares side‑by‑side items and swaps when they are out of order. Each pass pushes the largest remaining item to the end.
Analogy
Think of bubbling air bubbles in water: the biggest bubble rises to the top with each round.
Step-by-step
- Loop over the list, compare arr[j] and arr[j+1].
- Swap if the left item is larger.
- After one pass, the largest item is locked at the end.
- Shorten the next pass because the tail is already sorted.
- Stop early if no swaps occur in a pass.
Visual
Pass 1: [5,3,8,1,2] → [3,5,1,2,8]; Pass 2 trims the last slot, and so on until sorted.
Common mistakes
- Forgetting to reduce the inner-loop bound (wasted comparisons).
- Using >= and losing stability when equal items swap.
- Not breaking early when a pass makes zero swaps.
Practice questions
- Trace Bubble Sort on an already sorted list and count comparisons with and without early exit.
- Show a case where Bubble Sort is stable and explain why.
- Modify Bubble Sort to sort descending without changing space complexity.
Time
O(n²) worst/average, O(n) best with early-exit flag
AI Wisdom