Selection sort makes a useful practice problem because you can follow each pass and count the comparisons. This guide works through those steps so you can explain why the comparison count grows as the square of the input size.
What Selection Sort Actually Does
Selection sort repeatedly finds the minimum element from the unsorted region and places it at the beginning of that region.
After the first pass, index 0 is correct. After the second pass, index 1 is correct. This repeats until the array is sorted.
- Pass 1 scans n elements
- Pass 2 scans n minus 1 elements
- Pass 3 scans n minus 2 elements
Why Time Complexity is O(n^2)
The comparison count is (n minus 1) plus (n minus 2), continuing down to 1. That sum is n multiplied by (n minus 1), divided by 2.
When we drop constants and lower order terms, Big O becomes O(n^2). This is true for best, average, and worst case.
Selection sort does the same number of comparisons even if the array is already sorted.
Where Selection Sort Can Still Be Useful
In modern production systems, we rarely choose selection sort for large datasets. But there are scenarios where fewer swaps are useful.
If swap operations are expensive relative to comparisons, selection sort can outperform some alternatives despite similar asymptotic complexity.
- Small arrays
- Memory constrained systems
- Teaching and interview communication
How to Explain it in an Interview
Start with intuition, then derive complexity from number of passes and work per pass. End with tradeoffs and practical alternatives.
Explain what happens during one pass before writing the formula. Then show how the work adds up across all the passes. This gives the interviewer a way to follow and question your reasoning.
