Selection Sort

Selection sort minimises the number of swaps (at most n − 1) by scanning for the minimum element each pass and placing it in position — but its rigid O(n²) comparison count never improves, even on sorted input.

3 min read Level 1/5 #dsa#sorting#selection-sort

What you'll learn

Implement selection sort and trace through its loop invariant
Explain why selection sort is not stable in its classic form
Compare its swap count advantage against its fixed O(n²) complexity

Selection sort divides the array into a sorted prefix and an unsorted suffix. On each pass it scans the entire unsorted suffix to find the minimum element, then swaps that minimum into the first position of the unsorted region. After n − 1 passes every element is in its correct place.

The Idea

The loop invariant is: after iteration i, the subarray arr[0..i] contains the i + 1 smallest elements in sorted order and will never be touched again. This invariant gives at most n − 1 swaps in total — a significant advantage when writes are expensive (e.g., flash memory). However, the number of comparisons is always n(n − 1)/2 regardless of the input order, so there is no early-exit optimisation.

JavaScript Implementation

function selectionSort(arr) {
  const n = arr.length;

  for (let i = 0; i < n - 1; i++) {
    // Find the index of the minimum in arr[i..n-1]
    let minIndex = i;
    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }

    // Swap the found minimum into position i
    if (minIndex !== i) {
      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
  }

  return arr;
}

console.log(selectionSort([64, 25, 12, 22, 11]));
// => [11, 12, 22, 25, 64]

Why It Is Not Stable

Consider the array [3a, 3b, 1] where 3a and 3b are both equal to 3 but must be distinguished. On the first pass the minimum is 1, so 3a is swapped with 1, producing [1, 3b, 3a]. The original order of the two 3s is now reversed — the algorithm is not stable. A stable variant can be implemented by shifting rather than swapping, but that costs O(n²) writes, eliminating the swap-count advantage.

Complexity

Case	Time	Space	Stable	In-Place
Best	O(n²)	O(1)	No	Yes
Average	O(n²)	O(1)	No	Yes
Worst	O(n²)	O(1)	No	Yes

Unlike bubble sort, there is no best-case improvement. Even a fully sorted array triggers the full inner loop scan every time.

When to Use It

Selection sort is rarely the right choice in practice. Its main niche is environments where writes are extremely costly and reads are cheap — it guarantees at most n − 1 writes, fewer than any other O(n²) sort. Otherwise, insertion sort is strictly better: it is stable, in-place, and adaptive.

Up Next

Insertion sort builds the sorted prefix one element at a time using shifts rather than minimum-finding scans, giving it a genuine O(n) best case.

Insertion Sort →