Which one of the following is the tightest upper bound that represents the…
2013
Which one of the following is the tightest upper bound that represents the number of swaps required to sort n numbers using selection sort?
- A.
O(log n)
- B.
O(n)
- C.
O(n log n)
- D.
O(n2)
Attempted by 50 students.
Show answer & explanation
Correct answer: B
Concept
Selection sort performs exactly one swap per pass of its outer loop: at the end of each pass it places one element (the minimum of the remaining unsorted part) into its final position. The number of swaps is therefore governed by the number of passes, not by the number of comparisons.
Application
For an array of n elements, the outer loop runs (n − 1) times.
In pass i, scan the unsorted suffix to find its minimum element.
Exchange that minimum with the element at the current boundary — this costs at most one swap.
Across all passes the total number of swaps is at most (n − 1).
Asymptotically, (n − 1) = O(n).
Cross-check
The swap count is independent of the comparison count. Selection sort always performs Θ(n2) comparisons, yet the swaps grow far more slowly. The swap bound is tight because, in the worst case, every pass does require a genuine swap.