Overview
Selection Sort builds the sorted array one element at a time. On each pass it scans the unsorted portion, finds the smallest remaining value, and swaps it into the next sorted position.
How Selection Sort works
- Treat the whole array as unsorted and point to its first index.
- Scan the unsorted portion to find the index of the minimum value.
- Swap that minimum into the current position, growing the sorted prefix by one.
- Advance to the next position and repeat until the array is sorted.
When to use it
- Situations where the cost of writing/swapping must be minimised — it performs at most n−1 swaps.
- Small arrays or teaching, where its simple, predictable behaviour is an advantage.
Complexity analysis
Selection Sort always scans the entire unsorted portion, so it runs in O(n²) time in every case, with no early exit. Its saving grace is a minimal O(n) number of swaps. It is in-place (O(1) space) but not stable in its usual array form.
Frequently asked questions
How is Selection Sort different from Bubble Sort?
Both are O(n²), but Selection Sort makes far fewer swaps (one per pass) by selecting the minimum, whereas Bubble Sort swaps repeatedly within each pass.