Selection Sort: Mechanism, Complexity Analysis & Interactive Visualizer

Selection Sort

Find the smallest element in the unsorted region, swap it to the front, and shrink the region. Minimum writes among the simple sorts.

How it works

Selection Sort walks the array k − 1 times. Each pass scans the entire unsorted suffix to find the minimum value, then makes a single swap to put it in its correct final position.

1. Set i = 0.
2. Scan arr[i..n-1] to find the index min of the smallest value.
3. Swap arr[i] and arr[min].
4. Increment i and repeat.

The defining property: at most n − 1 swaps total. This makes Selection Sort attractive when writes are expensive (e.g., flash memory) even though it still does Θ(n²) comparisons.

Complexity

Interactive visualization

Pseudocode

procedure selectionSort(A):
  n ← length(A)
  for i from 0 to n − 2:
    min ← i
    for j from i + 1 to n − 1:
      if A[j] < A[min]: min ← j
    swap A[i], A[min]

JavaScript implementation

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

Pros and cons

When to use it

• Flash storage / EEPROM where write count matters more than comparisons.
• Teaching the concept of an "unsorted region" that shrinks each iteration.
• Very small arrays where simplicity beats sophistication.