An array of 1,000 elements is already perfectly sorted. How many comparisons does selection sort make?
AZero — it detects the sorted order and terminates early
BAbout 1,000 — one per element to verify it is in place
C499,500 — the same n(n−1)/2 it would make on any input
DAbout 500,000, but fewer than for a reversed array
Selection sort always makes exactly n(n−1)/2 comparisons regardless of the input's initial order. On each pass it scans the entire unsorted portion to find the minimum — it has no mechanism to detect that elements are already in order. This contrasts sharply with insertion sort, which degenerates to O(n) on already-sorted data. Selection sort simply does not adapt.
Question 2 Multiple Choice
You are sorting records stored in flash memory, where each write operation physically degrades the storage medium. Which property of selection sort makes it most appropriate for this context?
ASelection sort is O(n log n) in the best case, minimizing total operations
BSelection sort is stable, preserving the original order of equal-key records
CSelection sort makes exactly n−1 swaps, minimizing the number of write operations
DSelection sort runs entirely in-place, requiring no additional flash memory
Selection sort's defining property is that it makes exactly n−1 swaps — one per pass, not per comparison. No comparison-based sort makes fewer swaps. When writes are expensive (flash memory wears out; each swap triggers a costly side effect), this minimal-write property is decisive. Option B is a misconception: selection sort is NOT stable in its standard form. And option A is wrong: selection sort is O(n²) in all cases.
Question 3 True / False
Selection sort makes exactly n−1 swaps to sort an array of n elements, regardless of the initial ordering.
TTrue
FFalse
Answer: True
Selection sort performs one swap per pass: find the minimum of the unsorted region and swap it into position. With n elements there are n−1 passes (the last element is trivially in place), so exactly n−1 swaps occur. This holds whether the array starts sorted, reversed, or random — even a sorted array triggers n−1 swaps of elements with themselves. This is selection sort's key advantage when write cost dominates.
Question 4 True / False
Selection sort is generally faster than insertion sort on nearly-sorted input because selection sort makes fewer swaps.
TTrue
FFalse
Answer: False
This is the classic misconception. On nearly-sorted input, insertion sort runs in near-O(n) time because each element is close to its correct position and the inner loop exits early. Selection sort ignores existing order completely — it always makes n(n−1)/2 comparisons and n−1 swaps. On nearly-sorted data, insertion sort decisively outperforms selection sort. The swap-minimization advantage of selection sort is relevant only when write cost (not total operation count) is the bottleneck.
Question 5 Short Answer
Explain why selection sort's time complexity is O(n²) in the best case, even when the input is already sorted. What algorithmic property causes this?
Think about your answer, then reveal below.
Model answer: Selection sort has no mechanism to detect or exploit existing order. On each pass it must scan the entire unsorted portion to find the minimum — even if that minimum is already in the correct position. It compares every remaining element against the current candidate before confirming which element to swap. This scan always takes O(n) per pass and there are O(n) passes, giving O(n²) regardless of input.
The root cause is that selection sort's inner loop has no early-exit condition. The algorithm commits to finding the true minimum of the unsorted region, which requires exhaustive comparison. Insertion sort, by contrast, shifts elements right only until it finds the correct insertion point — on a sorted array the inner loop exits immediately after zero shifts, giving O(1) work per element and O(n) total.