Overview
Selection Sort scans the unsorted part to pick the smallest element and swaps it into the current position.
Analogy
Lining up by height: find the shortest person and move them to the front, then repeat.
Step-by-step
- For i from 0 to n-2:
- Set minIndex = i.
- Scan j from i+1 to n-1; if arr[j] < arr[minIndex], update minIndex.
- Swap arr[i] and arr[minIndex] once after the scan.
- Prefix [0..i] is sorted after each pass.
Visual
[8 3 5 1] → pick 1 swap with 8 → [1 3 5 8]; next pass picks 3, done.
Common mistakes
- Swapping every time a smaller value is found instead of once per pass.
- Forgetting Selection Sort is unstable unless you shift instead of swap.
- Using > instead of < during min search, flipping order.
Practice questions
- Count comparisons and swaps for n=5 sorted input.
- Modify to place max at the end each pass (descending).
- Make Selection Sort stable using insertion instead of swap.
Time
O(n²) comparisons, O(n) swaps
AI Wisdom