What is Selection Sort?
Learn how selection sort works, its O(n²) time complexity, why it minimizes swaps, and how to answer this interview question.
Expected Interview Answer
Selection sort repeatedly scans the unsorted portion of an array to find the minimum element and swaps it into place at the front, giving an O(n²) comparison-based sort that makes at most O(n) swaps.
On each pass, the algorithm scans the remaining unsorted suffix, tracks the index of the smallest value seen, and performs exactly one swap once the scan finishes, placing that minimum at the boundary between sorted and unsorted regions. This means selection sort always performs n-1 passes and roughly n²/2 comparisons regardless of the input order, so best and worst case are both O(n²). Its one redeeming property is a low, predictable number of writes — useful when swaps are expensive, such as writing to flash memory. It is not stable in its naive form because a swap can move an equal element past another equal element.
- Simple to implement and reason about
- At most O(n) swaps total
- Works in place with O(1) extra space
- Predictable performance regardless of input order
AI Mentor Explanation
A groundskeeper lining up trophies from smallest to largest walks the entire remaining shelf every single time just to find the smallest trophy left, then carries it to the front spot. Once placed, that spot is locked and the groundskeeper repeats the full remaining-shelf scan for the next smallest, never skipping ahead. Even if the shelf started almost in order, the groundskeeper still walks every remaining trophy on every pass, so the work never shrinks based on luck. The one upside is that each trophy only gets physically moved once per pass, which matters if the trophies are heavy and awkward to carry.
Step-by-Step Explanation
Step 1
Scan the unsorted suffix
Starting from the current boundary, scan every remaining element to track the index of the minimum.
Step 2
Swap into place
After the full scan, swap the minimum element with the element at the current boundary position.
Step 3
Advance the boundary
Move the sorted/unsorted boundary one position to the right and repeat.
Step 4
Stop after n-1 passes
Once only one element remains unsorted, it is already in its correct final position.
What Interviewer Expects
- State O(n²) time in best, average, and worst case
- Explain the algorithm always does the same number of comparisons regardless of input order
- Note at most O(n) swaps, which is its main practical advantage
- Acknowledge it is not stable in its basic form
Common Mistakes
- Claiming a best-case O(n) like insertion sort has on nearly sorted input
- Confusing selection sort with bubble sort’s adjacent-swap mechanism
- Forgetting selection sort is not stable by default
- Overstating its practical usefulness on large datasets despite the low swap count
Best Answer (HR Friendly)
“Selection sort works by repeatedly scanning the unsorted part of the list to find the smallest remaining item and moving it into place. It is simple to explain and only moves data a small number of times, but it always takes the same amount of comparisons no matter how the list started, so it does not scale well to large datasets.”
Code Example
def selection_sort(arr):
n = len(arr)
for i in range(n - 1):
min_index = i
for j in range(i + 1, n):
if arr[j] < arr[min_index]:
min_index = j
if min_index != i:
arr[i], arr[min_index] = arr[min_index], arr[i]
return arr
print(selection_sort([5, 2, 4, 1, 3])) # [1, 2, 3, 4, 5]Follow-up Questions
- Why does selection sort always run in O(n²), even on sorted input?
- How would you make selection sort stable?
- How does selection sort compare to bubble sort in number of swaps?
- When would the low swap count of selection sort matter in a real system?
MCQ Practice
1. What is the best-case time complexity of selection sort?
Selection sort always scans the full remaining unsorted suffix each pass, so best case equals worst case at O(n²).
2. What is the maximum number of swaps selection sort performs on an array of n elements?
Selection sort performs exactly one swap per pass, so at most n-1 swaps total, which is O(n).
3. Is the basic implementation of selection sort stable?
Swapping the minimum into place can move an equal element past another equal element, breaking stability by default.
Flash Cards
What does selection sort do on each pass? — Scans the unsorted suffix for the minimum, then swaps it into the current boundary position.
What is selection sort’s time complexity in all cases? — O(n²) — best, average, and worst case are all quadratic.
What is selection sort’s main practical advantage? — It performs at most O(n) swaps, useful when writes/swaps are expensive.
Is selection sort stable by default? — No — swapping the minimum into place can reorder equal elements.