GATE CS 2006 Q14 — Searching, Sorting, Hashing

The correct option is C.

To determine which in-place sorting algorithm requires the minimum number of swaps, let us analyze the swap complexity of each algorithm for an array of size $n$:

• Selection Sort: In each of the $n-1$ passes, the algorithm finds the minimum element from the unsorted part of the array and swaps it into its correct position. Therefore, it performs at most $n-1$ swaps in the worst, average, and best cases. Its swap complexity is strictly $\mathcal{O}(n)$.
• Insertion Sort: Typically shifts elements rather than swapping. However, if implemented using swaps, it requires $\mathcal{O}(n^2)$ swaps in the worst case and $\mathcal{O}(n^2)$ on average.
• Quick Sort: In the partition step, elements are swapped to position them relative to the pivot. The worst-case number of swaps is $\mathcal{O}(n^2)$ and the average-case is $\mathcal{O}(n \log n)$.
• Heap Sort: During the heapify and deletion phases, elements are repeatedly swapped. It requires $\mathcal{O}(n \log n)$ swaps in both the average and worst cases.

Since $\mathcal{O}(n)$ is asymptotically smaller than $\mathcal{O}(n \log n)$ and $\mathcal{O}(n^2)$, Selection Sort guarantees the minimum number of swaps among the given options.