CodeWithYash

Foundation · Module 4 · Lesson 1

Bubble Sort

Adjacent swaps and a growing sorted suffix.

15–25 min readLesson 19 of 123 Interactive Lab
Jump to interactive visualizer

Lesson 19 of 123

1d streak

Interactive Visualization

Trace the algorithm state by state

Change the inputs, run an operation, and connect each visible state change to the explanation below.

Step-through visualizer

Bubble Sort

Follow the state transition, then use the controls to test your prediction.

Orange cells are being compared. Green cells are already in their final suffix.
7
0
3
1
9
2
2
3
6
4
4
5
startBegin with the full array as the unsorted range.
Step 1 / 28

Theory lesson · Step-by-step

Understand Bubble Sort

Adjacent swaps and a growing sorted suffix.

Worked approach

Trace the reasoning step by step

  1. 1Identify the sorted region maintained by Bubble Sort.
  2. 2Choose or compare the next candidate according to the algorithm.
  3. 3Move values while preserving multiplicity and ordering requirements.
  4. 4Grow the sorted region and prove that at least one value becomes final.
  5. 5Check duplicates, stable-order requirements, sorted input, and reverse input.

Concrete example

Sort [5, 1, 4, 2] with adjacent swaps.

  1. 1Pass 1 moves 5 right → [1,4,2,5].
  2. 2Pass 2 → [1,2,4,5].
  3. 3No-swap pass stops early.

Each pass finalizes a sorted suffix.

What must remain true (Loop Invariant)

After each stage of Bubble Sort, the declared sorted region is final and the remaining values still contain every unplaced element.

Cost Model

Complexity & Trade-offs

Sort
O(n²), best O(n)
O(1)
The bound follows from the number of states visited and the work performed per transition.

When to use it

  • Creating order before searching, grouping, deduplicating, or scanning.
  • Selecting records using stability, memory, and input-shape constraints.
  • Turning pairwise decisions into monotonic scans.

Common mistakes

  • Comparing time alone while ignoring stability and auxiliary memory.
  • Breaking duplicate order when stability is required.
  • Quoting average performance without worst-case behavior.

Practice prompts

  • Reproduce the worked Bubble Sort example without looking at the trace.
  • Change one input condition and explain whether the Bubble Sort invariant still holds.
  • Implement the approach, derive its cost, and compare it with a straightforward baseline.

Mastery check

Can you derive it instead of memorizing it?

State the invariant before looking at code.
Explain why every transition is safe.
Construct a worst-case input.
Name one alternative and its trade-off.