1. One-Liner
Selection Sort maintains a growing sorted prefix by repeatedly selecting the smallest remaining element and swapping it into the next slot.
2. The Problem It Solves
You want a dead-simple O(n²) sort with at most O(n) swaps — helpful when writes are expensive compared to reads (e.g., flash).
3. The Core Idea
Pick the next smallest from the unsorted pile and place it after the sorted part — like repeatedly taking the lowest-numbered ticket from a hat.
4. How It Works (Step-by-Step)
| Step | What Happens |
|---|---|
| 1. | For i from 0 to n-2, treat 0..i-1 as sorted |
| 2. | Scan j = i..n-1 to find index m of the minimum value |
| 3. | Swap a[i] with a[m] |
| 4. | Increment i |
5. Dry Run Example
[7, 3, 9, 1] → min at end → swap with index 0 → [1, 3, 9, 7] → next min is 3 (in place) → then swap 9 and 7 → [1, 3, 7, 9].
6. Key Properties
| Property | Value |
|---|---|
| Swaps | O(n) total |
| Stable | No — long swaps break equal-key order |
| In-place | Yes |
7. Where It Is Used
| Company / System | How They Use It |
|---|---|
| Tiny embedded lists | When code size matters more than asymptotics |
| Teaching | Contrasts swap count with Bubble Sort |
8. Interview Tips
State clearly: always Θ(n²) comparisons even if sorted; contrast Insertion on nearly sorted data.
9. Comparison with Other Algorithms
| Algorithm | Swaps | Stable | Notes |
|---|---|---|---|
| Selection | O(n) | No | Few writes |
| Bubble | Many | Yes | More swaps |
| Insertion | O(n²) | Yes | Great if almost sorted |
10. Complexity
| Metric | Value |
|---|---|
| Time (Best) | O(n²) |
| Time (Average) | O(n²) |
| Time (Worst) | O(n²) |
| Space | O(1) |
| Stable? | No |
Implementation Example (PYTHON)
def selection_sort(arr):
n = len(arr)
for i in range(n - 1):
m = i
for j in range(i + 1, n):
if arr[j] < arr[m]:
m = j
arr[i], arr[m] = arr[m], arr[i]
return arr