GATE CS 2013 Q6 — Searching, Sorting, Hashing

In Selection Sort, the algorithm divides the array into a sorted and an unsorted region. In each of the $n-1$ passes, it performs the following steps:

1. Finds the minimum (or maximum) element in the unsorted subarray.
2. Swaps this minimum element with the first element of the unsorted subarray.

Since exactly one swap is performed per pass, the total number of swaps required to sort $n$ numbers is at most $n - 1$.

Therefore, the tightest upper bound for the number of swaps is $\mathcal{O}(n)$.

Comparison of Options:

• Option A ($\mathcal{O}(\log n)$): Too small; we need up to $n-1$ swaps in the worst case.
• Option B ($\mathcal{O}(n)$): Correct and the tightest upper bound.
• Option C ($\mathcal{O}(n \log n)$) and Option D ($\mathcal{O}(n^2)$): While these are valid upper bounds, they are not the tightest upper bounds for the number of swaps (though $\mathcal{O}(n^2)$ is the tightest upper bound for the number of comparisons).