GATE CSE 2006 | Question: 14, ISRO2011-14

Question

Which one of the following in place sorting algorithms needs the minimum number of swaps?

• A. Quick sort
• B. Insertion sort
• C. Selection sort
• D. Heap sort

Comments

ISRO has a pattern of asking every ambiguous previous year GATE question lol

---

In place algo i.e space O(1) but for this quick sort not applicable as it takes O(n)

am i correct?plz suggest any1.

---

in insertion sort we do half exchanges, i think they are counted as swaps in this question.

Answer 1

Correct Option: C - Selection sort.

Because in selection the maximum swaps which can take place are $O(n)$

Because we pick up an element an find the minimum (in case of forward sorting) from the next index till the end of array and than perform the swap

Hence, $O(n)$ whereas in all other algos the swaps are greater ( considering Worst-Case scenario )

Comments

partition (arr[], low, high)
{
    // pivot (Element to be placed at right position)
    pivot = arr[high];  
 
    i = (low - 1)  // Index of smaller element

for (j = low; j <= high- 1; j++) // no. of iterations=high-1-low+1
    {
        // If current element is smaller than or
        // equal to pivot
        if (arr[j] <= pivot)
        {
            i++;    // increment index of smaller element
            swap arr[i] and arr[j]
        }
    }
    swap arr[i + 1] and arr[high]) // +1 swap
    return (i + 1)
}

To understand my doubt please refer to the code above.

In the 1st level high=n and low=1. For the worst case of swapping, for each iteration there should be swapping. Hence total no. of swappings would be high-1-low+1=n-1-1+0=n-2 and outside the loop there is another swapping. Total swapping would be = n-1 in the 1st level. No. of swaps=O(n).

At 2nd level, if the pivot divides the array into equal halves then no. of swapping in this way is (low=1,high=(n/2)-1) so total swaps= (n/2)-1-1+1+1=n/2 and as there is another array set where low=n/2+1 and high=n so swaps=n/2 and hence total swaps=n.

If pivot element is placed at the end (for sorted array) then, low=1, high=n-1 so swaps= high-1-low+1+1=(n-1)-1-1+1+1=n-1.

We can assume that at each level the no. of swaps is O(n).

No. of levels= logn.

Total no. of swaps = nlogn.

How will it be n^2 @Bikram Sir ?

---

Sir in worst case, number of levels in quick sort is n .

Number of swaps in 1st level = n-1. In 2nd level n-2  and so on.

Total swaps= (n-1)+(n-2)+....+1=n(n-1)/2

= no of inversions

---

But in insertion sort we just shift the elements and we do not swap them right?

by that way answer has to be insertion sort...please anyone clear my doubt

Answer 2

Let's try to analyse the number of swaps in each of the given sorting algorithms. Quick sort – Worst Case input for maximum number of swaps will be already sorted array in decreasing order. Recurrence for Total number of swaps in this case : T(n) = T(n-1) + O(n) // O(n) swaps will occur in alternate calls to partition algorithm. = O(n2) Insertion sort - Worst Case input for maximum number of swaps will be already sorted array in ascending order.When a new element is inserted into an already sorted array of k size, it can lead to k swaps (in case it is the smallest of all) in worst case. For n-1 iterations of insertion sort, total swaps will be O(n2). Selection sort – There is no Worst case input for selection sort. Since it searches for the index of kth minimum element in kth iteration and then in one swap, it places that element into its orrect position. For n-1 iterations of selection sort, it can have O(n) swaps. Heap sort – Total number of swaps in Heap sort can be O(nlogn) as after performing Build-heap which may require O(n) swaps, it performs n-1 extract-min operations resulting into O(nlogn) swaps.

Comments

Insertion sort - Worst Case input for maximum number of swaps will be already sorted array in descending order. Please edit it.

---

Politically correct, it depends on which order sorting would be performed using Insertion Sort! Like sorting them in NON DECREASING ORDER (I. E. INCREASING ORDER) ​​​​​, then worst case will be array elements sorted in NON INCREASING ORDER (I. E. DECREASING ORDER).

 

And, vice versa. If one can't get what I meant above, read it thrice. Most probably one will easily get what I meant. Else, just reply back here. 

Answer 3

Number of swaps
Quick sort = $\Theta (nlogn)$
Insertion sort =  $\Theta (n^{2})$
Selction sort = no swaps required since we are shifting elements in the array and not swapping
Heap sort =  $\Theta (nlogn)$

Option C

Comments

@Aks9639

Can u check comment of reena?

Where is she  wrong?

---

@srestha mam , 

the first line that said by @reena_kandari has no problem at all , In worst case, if we got bad partitioning the number of swaps would be O(N^2) in QSort. Let say input (1,2,3,4,5) first pivot should be 5, next one 4, next one 3 and so on......hence total 5+4+3+2+1=15 => 5(5+1)/2 number of comparisons made, more precisely we can say N(N+1)/ 2 i.e. O(N^2).

but 

in worst case we have to do only n Logn swaps like 9,2,4,5,6,7,8

in this line I'm not getting what actually she is saying, if she talks about Qsort then in avg case Qsort takes NlogN swaps not in worst case. In worst case it should be O(N^2). So this would be an avg not worst. But if she talked about for general sorting, then it should be completely wrong.

Because

Insertion sort => in best case (already sorted) input takes like 1,2,3,4,5 there is no swaps happen it would be O(1) since data is already sorted. But in worst case like 5,4,3,2,1 it takes 1+2+3+4 precisely (N-1)N / 2 i.e again O(N^2).

Heap Sort => O(NlogN)  all cases.

but in Selection Sort => we either swap smallest element to fist element , then 2nd smallest to 2nd element of array and so on...or largest element to last one, 2nd largest to N-1th element and so on. 

hence it take O(N) number of swaps in all cases.

 

---

In quick sort no. of swappings :

case 1) [1,2,3,4,5] , last element as pivot

             no. of swappings = 5+4+3+2+1  {when 5 is pivot then 1,2,3,4 are swapped with itself, similarly for others}

                                         = (n-1)+(n-2)+.......+2+1            

                                         = (n(n-1))/2

                                         = O(n^2)

 

case 2)[5,4,3,2,1] , last element as pivot

                no. of swappings =  1 + 1 + 1 + 1 + 1

                                            = (n)

                                            =O(n)

                    eg: [5,4,3,2,1]                             {1 is pivot, 1 and 5 will be swapped}

                          [1] [4,3,2,5]                           {5 is pivot, 5 will be swapped with itself}  

                          [1] [4,3,2] [5]                         {2 is pivot, 4 and 2 will be swapped}

                          [1] [2][3,4] [5]                        {4 is pivot, 4 will be swapped with itself}

                          [1] [2] [3] [4] [5]                     {3 is pivot, 3 will be swapped with itself}  

case 3) [2,2,2,2,2], last element as pivot

                  no. of swappings =  1 + 1 + 1+ 1 +1

                                              = n

                                              = O(n)  

Am I correct ???? and in best case is no of swappings = O(log n) ???

Answer 4

Number of swaps : Worst case scenario 

1. Quick sort = O(n2)
2. Insertion sort = О(n2) 
3. Selection sort = O(n)
4. Heap sort = O(n logn)