GATE CS 2009 Q11 — 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 finds the minimum element from the unsorted region and swaps it with the element at the beginning of the unsorted region.

Key points regarding the complexity of Selection Sort:

• Comparisons: To find the minimum element in each pass, we perform comparisons. The total number of comparisons is always:
  $$\sum_{i=1}^{n-1} i = \frac{n(n-1)}{2} = \Theta(n^2)$$
• Swaps: In each of the $n-1$ passes, at most one swap is performed to place the minimum element in its correct position.

Thus, even in the worst case, the total number of swaps is at most $n-1$, which is $\Theta(n)$.

Therefore, the correct option is (A).