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

Selection Sort

← Part 1: Bubble Sort · Selection Sort (here) · Part 3: Insertion Sort →

Goal of the day

Implement selection sort from scratch: repeatedly find the minimum, swap it into place.
Understand why it does far fewer swaps than bubble sort, but no fewer comparisons.
Recognize its signature: a growing sorted prefix, built from the front by selection, not by insertion.

Concept

Scan the entire unsorted portion of a hand of cards to find the smallest one, then swap it into the very front position. Now the front card is locked in forever — scan the remaining unsorted portion for its minimum, swap that into the second position, and so on. Unlike bubble sort's "compare and swap next-door neighbors" motion, selection sort scans the whole remaining range every single pass, but only ever swaps once per pass — right at the end, once the minimum is found.

Diagram

Interactive visualization

comparing current minimum swapping in final position

Press Play or Step to begin.

The code

function selectionSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    let minIdx = i;
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[minIdx]) minIdx = j;
    }
    if (minIdx !== i) [arr[i], arr[minIdx]] = [arr[minIdx], arr[i]];
  }
  return arr;
}

Line by line:

minIdx tracks the smallest value's position as the inner loop scans the remaining unsorted range starting at i.
The swap happens at most once per outer-loop iteration, at the very end — this is why selection sort does far fewer swaps than bubble sort, even though it does just as many comparisons.

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

i	Scan finds min	Swap	Array after
0	1 (index 3)	swap(0, 3)	[1, 2, 8, 5]
1	2 (index 1)	no swap needed	[1, 2, 8, 5]
2	5 (index 3)	swap(2, 3)	[1, 2, 5, 8]

Only 2 swaps total for 4 elements — bubble sort would typically need more, since it swaps on nearly every out-of-order comparison.

Complexity

Time (best)	Time (worst)	Space	Stable?
O(n²) — always fully scans, even if sorted	O(n²)	O(1)	No

Unlike bubble or insertion sort, selection sort has no fast path for nearly-sorted input — it always scans the full remaining range on every pass, whether or not that scan finds anything to change.

Interview corner

Which sort minimizes the number of swaps? Selection sort — exactly n−1 swaps in the worst case, since it swaps at most once per outer-loop pass. Bubble sort (Part 1) can swap on nearly every comparison.
⚠ Trap: "fewest swaps" doesn't mean "fastest" — selection sort still does O(n²) comparisons regardless of how sorted the input already is, so it never gets a best-case speedup the way bubble or insertion sort can.
Is selection sort stable? Not in its naive form — swapping a found minimum into place can jump it past an equal element, changing their relative order.
↳ Common follow-up: "How would you make it stable?" — instead of swapping, shift all elements between the old and new positions over by one and insert the minimum — more work, but preserves order.
When would selection sort's low swap count actually matter? When writes are much more expensive than reads/comparisons — for example, sorting data on flash memory where each write wears down the hardware. A niche case, but a good one to mention if asked "when would you ever choose this."

How to talk through it out loud: state the invariant — "after pass i, the first i elements are the i smallest elements in the array, in sorted order." Naming that invariant is what shows you understand why the algorithm is correct, not just that you memorized the loop shape.

Practice problems

1. Third Maximum Number (Easy — LeetCode: Third Maximum Number)

Given an array of integers, return the third distinct maximum value. If it doesn't exist, return the maximum value.

function thirdMax(nums) {
  const top = [-Infinity, -Infinity, -Infinity];
  for (const n of nums) {
    if (top.includes(n)) continue;
    if (n > top[0]) { top[2] = top[1]; top[1] = top[0]; top[0] = n; }
    else if (n > top[1]) { top[2] = top[1]; top[1] = n; }
    else if (n > top[2]) { top[2] = n; }
  }
  return top[2] === -Infinity ? top[0] : top[2];
}

2. Maximum Product of Two Elements in an Array (Easy — LeetCode: Maximum Product of Two Elements in an Array)

Given an array, find the two largest values and return (max1 − 1) × (max2 − 1).

function maxProduct(nums) {
  let max1 = -Infinity, max2 = -Infinity;
  for (const n of nums) {
    if (n > max1) { max2 = max1; max1 = n; }
    else if (n > max2) { max2 = n; }
  }
  return (max1 - 1) * (max2 - 1);
}

3. Kth Largest Element in an Array (Medium — LeetCode: Kth Largest Element in an Array)

Find the kth largest element in an unsorted array.

// Selection-sort-style approach — O(n·k), appropriate for today's topic.
// A heap (Day 22) gets this to O(n log k); quickselect averages O(n).
function findKthLargest(nums, k) {
  const arr = [...nums];
  for (let i = 0; i < k; i++) {
    let maxIdx = i;
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] > arr[maxIdx]) maxIdx = j;
    }
    [arr[i], arr[maxIdx]] = [arr[maxIdx], arr[i]];
  }
  return arr[k - 1];
}

Quiz

1. Compared to bubble sort, selection sort minimizes:

2. What's selection sort's BEST-CASE time complexity?

3. Is naive (swap-based) selection sort stable?

4. What does minIdx track in the inner loop?

5. Selection sort's low swap count matters most when:

Continue to Part 3: Insertion Sort →