Day 8a: Bubble Sort

DAY 8 / 30 · WEEK 2 · PART 1 OF 3

Day 8 covers three O(n²) sorts in three short parts: Bubble Sort (here) → Selection Sort → Insertion Sort.

Goal of the day

• Implement bubble sort from scratch: compare neighbors, swap if out of order.
• Understand why it’s O(n²), and how one small optimization gives it an O(n) best case.
• Recognize its visual “signature” — the largest unsorted value sinks to the end each pass.

Concept

Imagine sorting a hand of playing cards by repeatedly walking down the hand comparing each pair of neighbors, swapping any pair that’s out of order. Every full walk pushes the largest remaining card as far right as it can go — like a bubble rising to the surface, which is where the name comes from. Walk the hand again, and the next-largest card sinks into place. Repeat until a full walk makes zero swaps — at that point, everything is sorted.

Diagram

Interactive visualization

Running example: arr = [5, 2, 8, 1, 9, 3]

Press Play or Step to begin.

Step 0 / 28

▶ Play⏭ Step↺ Reset🔀 Shuffle

The code

function bubbleSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    let swapped = false;
    for (let j = 0; j < arr.length - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        swapped = true;
      }
    }
    if (!swapped) break; // a pass with zero swaps means the array is already sorted
  }
  return arr;
}

Line by line:

• The inner loop’s upper bound shrinks by one each pass (arr.length - 1 - i) because the last i elements are already guaranteed sorted from previous passes — no need to recheck them.
• The swapped flag is what gives bubble sort its O(n) best case: on an already-sorted array, the first pass makes zero swaps, so we break immediately instead of running n more wasted passes.

Dry run: bubbleSort([5, 2, 8, 1])

Pass	Compare	Swap?	Array after
1	5, 2	Yes	[2, 5, 8, 1]
1	5, 8	No	[2, 5, 8, 1]
1	8, 1	Yes	[2, 5, 1, 8]
2	2, 5	No	[2, 5, 1, 8]
2	5, 1	Yes	[2, 1, 5, 8]
3	2, 1	Yes	[1, 2, 5, 8]

Notice 8 reaches its final position after pass 1 and is never touched again — each pass needs to check one fewer element than the last.

Complexity

Time (best)	Time (worst)	Space	Stable?
O(n) — with the swapped-flag early exit	O(n²)	O(1)	Yes

“Stable” means equal elements keep their original relative order. Bubble sort only ever swaps adjacent elements, so two equal values never leapfrog each other.

Interview corner

Is bubble sort ever actually used in production? Almost never — it’s taught because the swap-neighbors mechanic is foundational, not because it’s competitive. Being honest about this in an interview (“I know this isn’t production-grade, but here’s why it’s worth understanding”) reads better than pretending it’s a real choice.

↳ Common follow-up: “So what would you actually use?” — Day 10/11’s O(n log n) sorts, or for small/nearly-sorted inputs, insertion sort (up next after selection sort).

What’s bubble sort’s worst case? A reverse-sorted array — every single comparison results in a swap, for the full O(n²) comparisons and O(n²) swaps.

⚠ Trap: the swapped-flag optimization only helps the best case (already sorted). It does nothing for the worst case — don’t claim it changes bubble sort’s fundamental O(n²) classification.

Why does bubble sort get its name? Larger values move toward the end of the array one swap at a time, the way a bubble rises toward the surface of water — each pass, the largest remaining value “bubbles up” (rightward) to its final position. It’s a mnemonic for the motion, not a technical property.

How to talk through it out loud: name the invariant bubble sort maintains — “after pass i, the last i elements are guaranteed to be in their final sorted position.” Stating the invariant is what proves you understand why the algorithm terminates correctly, not just that you memorized the loop structure.

Practice problems

Squares of a Sorted Array

Easy — LeetCode: Squares of a Sorted Array

Given a sorted array (possibly with negative numbers), return the squares of every element, also sorted.

Hint: You could square everything and sort — O(n log n) — but the biggest squares always come from the two ends of the original sorted array. Can you use Day 4’s two-pointer idea instead, for O(n)?

Solution:

function sortedSquares(nums) {
  // Simple O(n log n) version, appropriate for today's topic:
  return nums.map((n) => n * n).sort((a, b) => a - b);
}
// The O(n) two-pointer version is genuinely Day 4 material —
// not repeated here, but worth revisiting once that pattern is solid.

Check if Array Is Sorted and Rotated

Easy — LeetCode: Check if Array Is Sorted and Rotated

Given an array, return true if it could have been produced by taking a sorted array and rotating it some number of positions.

Hint: Walk adjacent pairs, wrapping from the last element back to the first — exactly the neighbor-comparison mechanic from today. How many times can a sorted-and-rotated array “drop” (a value followed by a smaller one)?

Solution:

function check(nums) {
  let drops = 0;
  const n = nums.length;
  for (let i = 0; i < n; i++) {
    if (nums[i] > nums[(i + 1) % n]) drops++;
  }
  return drops <= 1;
}

Sort Colors

Medium — LeetCode: Sort Colors

Given an array with only the values 0, 1, and 2, sort it in place.

Hint: Only 3 possible values means you don’t need a comparison sort at all — count how many 0s, 1s, and 2s there are, then overwrite the array in that order.

Solution:

function sortColors(nums) {
  const counts = [0, 0, 0];
  for (const n of nums) counts[n]++;
  let idx = 0;
  for (let color = 0; color < 3; color++) {
    for (let k = 0; k < counts[color]; k++) nums[idx++] = color;
  }
  return nums;
}

Quiz

Quiz: Bubble sort’s signature move each pass is:

The largest unsorted element sinks to its final position at the end

Each full pass of neighbor-swapping pushes the largest remaining value as far right as it can go — the ‘bubble rising’ signature.

Quiz: What’s bubble sort’s WORST-CASE time complexity?

O(n²)

A reverse-sorted array forces every comparison to result in a swap — O(n²) in the worst case.

Quiz: What’s bubble sort’s BEST-CASE time complexity, with the swapped-flag optimization?

O(n)

The swapped-flag lets bubble sort break out after the first pass if nothing needed swapping — close to O(n).

Quiz: Is bubble sort stable (do equal elements keep their original order)?

Yes — adjacent-only swaps never let equal elements leapfrog each other

Bubble sort only swaps adjacent elements, so two equal values are never moved past each other — that’s what makes a sort stable.

Quiz: How commonly is bubble sort used in real production systems?

Almost never — it’s mainly a teaching tool

Bubble sort is taught for the foundational swap-neighbors mechanic, not because it’s competitive with O(n log n) sorts in real systems.

---

Continue to Part 2: Selection Sort →