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

swaps

 

 

---

I have one Silly doubt - Insertion do not swap the elements it stores the current element in the variable lets say key and shift the elements based on if it is greater than key or not, So can we say insertion sort requires 0 swaps ?

But there is also one example like - Sort - 5,2,3,4. the intermediate steps will be 2,5,3,4 => 2,3,5,4 => 2,3,4,5. in this the shift operations act exactly like swap. So can we conclude swap == shift in this type examples ??

---

@The.CSE.Guy yes i think , insertion sort also do a lot of movements of array elements while Selection sort is clean just do n swap for n elements.

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) 

Answer 5

Answer: Selection sort.

---

Explanation

• Selection sort always performs exactly n−1 swaps (for an array of size nn):
  In each of the n−1 passes, it finds the minimum element in the unsorted portion and swaps it into place.
  Thus, regardless of the input’s initial order, it does exactly n−1 exchanges.

• Insertion sort (when implemented via shifting instead of swapping) moves elements by “shifting” them one position at a time, which typically results in up to Θ(n^2) element moves in the worst case.
  If you instead implement insertion sort by repeatedly swapping adjacent elements until the new element reaches its correct spot, it can use Θ(n^2) swaps in the worst case (for example, if the input is reverse‐sorted).

• Heap sort builds a heap in O(n) time and then repeatedly swaps the root with the last element and “heapifies” the root down. In the worst case, each of the n removals from the heap costs one swap to move the max element to the end plus up to log⁡n more swaps to restore the heap property—so on the order of Θ(nlog⁡n) swaps overall.

• Quick sort (in its in‐place, two‐pointer partitioning form) also uses Θ(nlog⁡n) comparisons on average because when partition algorithm does n swaps atmost to place the pivot element at place and that recursive call is made logn times.( There are logn levels with each level summing size of n ) hence nlogn swaps at worst.

Because selection sort uses exactly n−1 swaps no matter what, while all of the other in-place algorithms here can require on the order of nlog⁡n or even n^2 swaps in the worst case, selection sort has the minimum (and tightly bounded) number of swaps.