About Selection Sort
Selection Sort divides the array into a sorted region at the front and an unsorted region behind it. On each pass it scans the entire unsorted region to find its minimum, then swaps that minimum into the first unsorted slot. It always performs exactly n(n-1)/2 comparisons regardless of the input, and uses at most n-1 swaps — the fewest writes of any simple sort. It is simple and in-place, but not stable and not adaptive, so it is mainly of educational value.
Complexity Analysis
- Time Complexity
- O(n²)
- Space Complexity
- O(1)
- Difficulty
- beginner
Key Concepts
Select the Minimum
Each pass finds the smallest element of the unsorted region and places it at the front. After pass i, the first i+1 elements are in their final sorted positions.
Comparisons vs. Swaps
Selection Sort always makes the same number of comparisons — n(n-1)/2 — but only up to n-1 swaps. When writing to memory is expensive, its low swap count is an advantage over Bubble Sort.
Not Stable, Not Adaptive
Swapping a far-away minimum into place can reorder equal elements, so Selection Sort is not stable. It also does the same work on sorted and unsorted input, so it is not adaptive.
Common Pitfalls
Assuming it is faster on sorted input
Unlike Insertion Sort, Selection Sort scans the whole unsorted region every pass, so an already-sorted array still costs O(n²) comparisons.
Expecting stability
Selection Sort is not stable. If stability matters (e.g. sorting records by one field), use Insertion Sort or Merge Sort instead.