PA of Algorithms Q85
- Option : C
- Explanation : Given: n numbers To find: Tightest upper bound on number of swaps required to sort n numbers using selection sort. Analysis: In selection sort, in the unsorted part of the array, we find the minimum element and swap it with the value placed at the index where the unsorted array starts. Hence, for each element to put it in its sorted position, we will do some swaps. In each iteration, when we find the minimum and place it in its sorted position, we do only one swap. There are n such iterations, since maximum number of positions to sort is n. Hence, there are n.O(1) swaps ⇒ O(n) swaps. ∴ The solution is (C)
