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)\)

Answer

Things you need to know

Refer : http://www.techtud.com/video-lecture/selection-sort-algorithm-and-analysis

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)

0Comment