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

Refer :

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)