##### GATE 2009 Example on Selection Sort

What is the number of swaps required to sort elements using selection sort, in the worst case?
A) $\Theta(n)$

B) $\Theta(\log n)$

C) $\Theta(n^2)$

D) $\Theta(n^2\log n)$

Things you need to know

Now, if you look at the algorithm of selection sort:

Void SelectionSort (int*arr, int n)
{
for (int i=0; i<n-1; ++i)
{
int minIdx = i;
for(int j = i+1; j<n; ++j)
{
if (arr[j] < arr[minIdx)
minIdx = j;
}
if (minIdx != i)
swap (arr, i, minIdx);
}
}  

We are finding the minimum among the numbers, in each iteration placing it at the appropritate position.

No. of swaps required to place one number at its proper position is = $\Theta(1)$

$\therefore$ For $n$ numbers total number of swaps required = $n*(\Theta(1)) = \Theta(n)$

Hence, Ans (A)