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

Bubble Sort

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

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])

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

"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

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.

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;
}

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