Selection Sort

How selection sort works

Imagine sorting a stack of papers by date. You scan the entire pile, find the oldest paper, place it at the front of a new pile. Then scan the remaining pile, find the next-oldest, place it in position 2. Repeat until the input pile is empty. That is selection sort, in a sentence.

The algorithm maintains a sorted prefix on the left of the array. Each outer iteration extends the prefix by one — by scanning the unsorted suffix, finding its minimum, and swapping that minimum into the boundary slot.

1. Loop i from 0 to n-2.
2. Set min_idx = i.
3. For j from i+1 to n-1: if arr[j] < arr[min_idx], set min_idx = j.
4. Swap arr[i] with arr[min_idx].

The key invariant: after iteration i, arr[0..i] is sorted and contains the i+1 smallest elements of the original array.

Trace through 5 elements

Sorting [64, 25, 12, 22, 11]. The bracket marks the sorted prefix:

Start:    [] 64 25 12 22 11

i = 0: scan [64, 25, 12, 22, 11], min = 11 at index 4
       swap arr[0] ↔ arr[4]:
       [11] 25 12 22 64

i = 1: scan [25, 12, 22, 64], min = 12 at index 2
       swap arr[1] ↔ arr[2]:
       [11 12] 25 22 64

i = 2: scan [25, 22, 64], min = 22 at index 3
       swap arr[2] ↔ arr[3]:
       [11 12 22] 25 64

i = 3: scan [25, 64], min = 25 at index 3
       swap arr[3] ↔ arr[3] (self-swap):
       [11 12 22 25] 64

Done:  [11 12 22 25 64]

Total: 10 comparisons (n(n−1)/2 = 10 for n=5), 4 swaps. Notice how comparisons are fixed regardless of input — selection sort is the only common O(n²) sort that's not adaptive.

When to use selection sort

• Writes are expensive. Selection sort does at most n−1 swaps. Compare to insertion sort's worst-case n²/2 shifts or bubble sort's n²/2 swaps. On flash memory (rated for ~100k writes per cell), this matters.
• Each swap is a network call. If you're sorting items by repeatedly asking a remote oracle to compare and reorder, you want the lowest possible swap count.
• Memory is rewritable but slow. EEPROMs, NVRAM, log-structured filesystems all benefit from minimizing writes.
• Pedagogy. The algorithm is dead simple — perfect for a first sorting lesson.

For general-purpose sorting? Almost never. Insertion sort outperforms it on every dimension except write count, and modern memory makes write count a niche concern.

Selection sort vs other O(n²) sorts

	Selection	Insertion	Bubble	Heapsort
Best case	O(n²)	O(n)	O(n)	O(n log n)
Average	O(n²)	O(n²)	O(n²)	O(n log n)
Worst case	O(n²)	O(n²)	O(n²)	O(n log n)
Comparisons	~n²/2 always	n−1 to n²/2	n−1 to n²/2	2n log n
Writes (worst)	3(n−1)	n²/2	n²/2	n log n
Stable	No	Yes	Yes	No
Adaptive	No	Yes	Yes	No
In-place	Yes	Yes	Yes	Yes
Best for	Minimizing writes	Small/sorted arrays	Teaching only	Worst-case guarantee

Selection sort wins exactly one column: write count. That's its entire reason to exist outside textbooks. Heapsort is selection sort with a heap-based way to find the minimum in O(log n) instead of O(n) — same algorithmic shape, dramatically better complexity.

What "O(n²) always" actually costs

Selection sort does n(n-1)/2 comparisons no matter what. On modern hardware, each comparison-and-conditional-update of min_idx costs about 2-4 ns:

n	Comparisons	Wall time (≈)	Swaps (worst)
10	45	0.2 µs	9
100	4,950	20 µs	99
1,000	499,500	2 ms	999
10,000	49,995,000	200 ms	9,999
100,000	~5×10⁹	~20 s	99,999

For comparison, sorting 10,000 random integers with selection sort takes ~200 ms; insertion sort averages ~250 ms (similar — both O(n²)) but quicksort lands at ~1 ms. The 200× gap is why we use O(n log n) sorts whenever writes aren't the bottleneck.

The flash-memory case: Suppose each cell write takes 100 µs (typical NAND flash). Insertion sort on 1000 elements does ~250,000 writes = 25 seconds of write time. Selection sort does ~3,000 writes = 0.3 seconds. The comparison-time difference is dwarfed.

JavaScript implementation

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

The if (minIdx !== i) check skips the self-swap. It's a tiny optimization but matters when writes are the cost — without it, sorting an already-sorted array still does n−1 self-swaps.

Sort-already-sorted edge case

// Selection sort is non-adaptive: comparisons are constant
// regardless of input order.
const sorted = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
selectionSort(sorted);  // 45 comparisons, 0 swaps (with skip-self check)

const reversed = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1];
selectionSort(reversed);  // 45 comparisons, 5 swaps (n/2 swaps for reversed)

// Note: even reverse-sorted only triggers ~n/2 swaps, not n-1.
// Selection sort's swap count depends on cycle structure of the
// permutation, not on inversion count.

Python implementation

def selection_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        min_idx = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        if min_idx != i:
            arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

# Demo: stable variant via insertion of the min, not swap.
# Costs O(n) per insertion → O(n²) total, but preserves order.
def stable_selection_sort(arr):
    result = list(arr)
    for i in range(len(result) - 1):
        min_idx = i
        for j in range(i + 1, len(result)):
            if result[j] < result[min_idx]:
                min_idx = j
        # Lift the min and re-insert at position i (preserves order)
        val = result.pop(min_idx)
        result.insert(i, val)
    return result

Double-ended selection sort

A variant that finds both the minimum and maximum on each pass, placing them at both ends of the unsorted region. The outer loop runs n/2 times instead of n times:

function doubleEndedSelectionSort(arr) {
  let lo = 0, hi = arr.length - 1;
  while (lo < hi) {
    let minIdx = lo, maxIdx = lo;
    for (let i = lo; i <= hi; i++) {
      if (arr[i] < arr[minIdx]) minIdx = i;
      if (arr[i] > arr[maxIdx]) maxIdx = i;
    }
    // Place min at lo
    [arr[lo], arr[minIdx]] = [arr[minIdx], arr[lo]];
    // The max might have just moved if it was at lo
    if (maxIdx === lo) maxIdx = minIdx;
    // Place max at hi
    [arr[hi], arr[maxIdx]] = [arr[maxIdx], arr[hi]];
    lo++;
    hi--;
  }
  return arr;
}

Same total comparisons (~n²/2), half the outer-loop iterations. The constant-factor speedup is real but small (~10-20%). The trickiest part is the if (maxIdx === lo) fixup — after swapping the min out of lo, the index where the max was sitting may now hold a different value.

Connection to heapsort

Selection sort wastes effort. Each pass scans the full unsorted suffix to find a single minimum, then throws away everything it learned about the rest. The fix: store the unsorted region in a data structure that remembers ordering between passes — a heap.

Heapsort is selection sort with the inner "find the min" replaced by a heap-extract-min. Heap construction is O(n); each extract-min is O(log n); n extracts cost O(n log n). The outer "place at position i" loop is unchanged. Read the heapsort writeup for the full transformation.

Common bugs and edge cases

• Inner loop starts at i instead of i+1. A wasted comparison every iteration — code still works but does (n−1)² comparisons instead of n(n−1)/2.
• Outer loop runs to n-1 instead of n-2. The last element is automatically in place when the prefix has n−1 sorted elements; the final iteration is wasted but harmless.
• Forgetting the self-swap skip. Without if (minIdx !== i), you write to flash memory n−1 times even when the array is already sorted — defeats the algorithm's main advantage.
• Stability mistake. Standard selection sort is unstable. If you need stable behavior, switch to the linked-list-style "lift and insert" variant (shown above) or use a different sort entirely.
• Using <= instead of < in the min check. The <= form picks the rightmost minimum, which doesn't break correctness but is a redundant write.