GATE CS 2013 Q.6 (CS Q.6): Searching and Sorting Algorithms

Which one of the following is the tightest upper bound that represents the number of swaps required to sort $n$ numbers using selection sort?

$O(\log n)$

$O(n)$

$O(n \log n)$

$O(n^2)$

Official answer and solution

Official answer: B
From: Official GATE 2013 answer key

Solution

Analyze the number of element swap operations executed during selection sort on an array of size n.

In standard selection sort:

The algorithm makes $n - 1$ passes across the array.
In the $i$ -th pass, it searches the remaining unsorted subarray for the minimum element and performs at most 1 swap to place that element into index $i$ .
Across all $n - 1$ passes, the maximum total number of swaps is at most $n - 1$ .

Therefore, the number of swaps is bounded by $O(n)$ .
(Note that while the number of comparisons is $\Theta(n^2)$ , the number of swaps is strictly $O(n)$ ).

Final answer

Option (B)

Common trap

Confusing the number of comparisons ( $O(n^2)$ ) with the number of swaps ( $O(n)$ ).

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2013 Computer Science and Information Technology (CS)
Question: 6 of 65, printed as CS Q.6
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source