Selection Sort maintains a sorted prefix on the left and an unsorted suffix on the right. It repeatedly scans the unsorted region for its minimum, then swaps that minimum to the boundary.

Imagine arranging books by size: instead of shuffling everything, repeatedly find the smallest remaining book and place it at the next spot on the left.

How It Works

1. Set the boundary of the sorted region at index 0.
2. Scan the entire unsorted sub-array to find the index of its minimum element.
3. Swap that minimum with the element currently at the boundary.
4. Advance the boundary one position to the right.
5. Repeat until the boundary reaches the last element — the array is sorted.

Key Insight

Selection Sort’s signature trait: at most n-1 swaps, regardless of input. Every other naive sort can swap far more often.

The cost: it always performs a full O(n²) scan — even on an already-sorted array. It is non-adaptive. Choose it only when writes cost far more than reads (e.g., flash memory with limited write endurance).

Worked Example

Sort [5, 3, 8, 1, 2] with Selection Sort:

• Boundary at 0: minimum of [5, 3, 8, 1, 2] is 1 at index 3 → swap → [1, 3, 8, 5, 2]
• Boundary at 1: minimum of [3, 8, 5, 2] is 2 at index 4 → swap → [1, 2, 8, 5, 3]
• Boundary at 2: minimum of [8, 5, 3] is 3 at index 4 → swap → [1, 2, 3, 5, 8]
• Boundary at 3: minimum of [5, 8] is 5 at index 3 → already in place, no-op
• Boundary at 4: single element left, done

Result: [1, 2, 3, 5, 8] with exactly 3 swaps. In the visualizer, watch how the scan marker sweeps the whole unsorted region before each swap happens.

Edge Cases & Pitfalls

• Already sorted input — still scans everything: always O(n²) comparisons, but zero or near-zero swaps.
• Single element / empty array — trivially sorted, no swaps.
• Duplicates — Selection Sort is unstable: a long-distance swap can move an equal element past another of the same value. If stability matters, prefer Insertion or Merge Sort.
• “Swap into place” trap — when the minimum is already at the boundary, skip the swap to avoid a wasted write.

Comparison With Other Sorts

Applications

• Situations where memory writes are the bottleneck (embedded systems, limited-write media)
• Small datasets where implementation simplicity beats speed
• Building blocks — selection’s “repeated minimum extraction” idea appears in heap sort (a heap finds the minimum faster)

Practice Trajectory

1. Hand-trace Selection Sort on [7, 2, 9, 1, 5], noting the boundary after each step.
2. Count the swaps for a reverse-sorted array of size 6 and explain why it is still ≤ n-1.
3. Construct a small array of duplicate values where Selection Sort changes their relative order.
4. Explain why Selection Sort cannot early-exit on a sorted array.
5. Implement it, then modify it to skip the swap when the minimum is already at the boundary.