What is the number of swaps required to sort n elements using selection sort,…
2009
What is the number of swaps required to sort n elements using selection sort, in the worst case?
(Α) Θ(n)
(B) Ө(n log n)
(C) Ө(n²)
(D) Ө(n² log n)
- A.
A
- B.
B
- C.
C
- D.
D
Attempted by 833 students.
Show answer & explanation
Correct answer: A
Answer: Θ(n) swaps (at most n−1 swaps in the worst case).
Selection sort algorithm: for each position i from 1 to n−1, find the minimum in the unsorted suffix and swap it into position i.
Each outer iteration performs at most one swap (swap the found minimum into place).
Therefore the maximum number of swaps is the number of outer iterations, n−1, which is Θ(n).
Note: selection sort still does Θ(n²) comparisons, but comparisons and swaps are different measures; the question asks about swaps.
A video solution is available for this question — log in and enroll to watch it.