GATE CSE
First time here? Checkout the FAQ!
x
+3 votes
2.7k views

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

  1. Quick sort
  2. Insertion sort
  3. Selection sort
  4. Heap sort
asked in Algorithms by Loyal (4k points)   | 2.7k views
Shouldn't this be Insertion Sort?

As in Insertion Sort, we "technically" don't swap, but shift elements to place the element under consideration in proper place
does swap here means shifting the elements??
NU OF SWAP
IN BUBBLE SORT =O(n2)
in selection sort=n
in insertion sort =0
In insertion sort (implementation like Cormen) we should use the term Movement or Shifting.
Number of swapping:   We cant say it is zero. Swappings are done indirectly. (Just check initially 2nd element is swapped with first, other swaps are done indirectly)
 
It should not be asked actually.  Because we do not swap anything directly.
Why it is asked in GATE again in ISRO?
I think if they are asking about swapping in insertion sort, then they are following that approach of insertion sort where swapping is done.
See this https://cs.stackexchange.com/questions/21455/how-can-i-quantify-the-number-of-swaps-required-for-insertion-sort
This approach where swapping is done is more popular as insertion sort.. See wiki.
In wiki, they also have written insertion sort with approach2(Cormen) & recursive one. They also have written 2nd approach is little bit faster. But they have analysed the complexity based on 1st approach..

In case of Insertion sort ,

best case is O(n) swaps , when the array is already sorted .

worst case O(n2) swaps 

source:wikipedia

@Bikram sir..  as per the 1st approach where swapping is done..  Best case O(n) swap.. Worst case O(n sq) swap.

As per 2nd approach (like Cormen)..  best case 0 movements.. Worst case n(n-1)/2 movements..   :)

@ahwan

in worst case :

n(n-1)/2 = (n2 - n) /2 which is nothing but O(n2)  :)

Swaps in approach 1 & movements in approach 2 in worst case are O(n sq)..  but in best case swaps for approach 1 is O(n) where as no movements are done in approach 2. By the way key replaces the number with itself.. But it is not movement I guess..
yes it is swap , replacing key is same as swapping .

3 Answers

+9 votes
Best answer
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 )
answered by (389 points)  
edited ago by
Please compare number of swaps in selection sort with other sorting techniques given in above question.

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) 

@Ahwan

In case of selection sort , number of swaps require :

Best case: No swaps required as all elements are properly arranged

Worst case: n-1 swaps required

Reference:

https://stackoverflow.com/questions/26688765/what-are-the-number-of-swaps-required-in-selection-sort-for-each-case

another source :

While selection sort is preferable to insertion sort in terms of number of writes

(Θ(n)  swaps versus Ο(n2) swaps),

That means selection sort has O(n) swaps while insertion sort have O(n2) swaps in worst case.

Reference :

https://en.wikipedia.org/wiki/Selection_sort#Comparison_to_other_sorting_algorithms

@bikram sir in selection sort, in best case also the number of swaps are O(n). In best case 1st smallest element will be A[1] itself and if we don't do any modification in the standard algorithm definition given in cormen then A[1] will be swapped with itself. Hence in each iteration element will be swapped with itself.

@vineet

In Best case , number of swaps are O(n) or 0 swaps , it really depends on the implementation .

And swapping with itself at first position only count as 0 swaps , as all elements are properly arranged .

What i read is in Best case number of swaps is 0 but it depends how selection sort is done..

for this gate question , no doubt answer is selection sort ..

You may read this answer , to get some idea https://stackoverflow.com/questions/26688765/what-are-the-number-of-swaps-required-in-selection-sort-for-each-case

+8 votes
(C) Selection sort
answered by Boss (6.2k points)  
+1 vote
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
answered by Active (1.6k points)  
in  quick  wont it be n^2 ?

Yes, for Quick Sort , worst case time complexity O(n2)

 on average, the algorithm takes O(n log n) comparisons to sort n items.

 



Top Users Jul 2017
  1. Bikram

    4062 Points

  2. manu00x

    2464 Points

  3. Debashish Deka

    1850 Points

  4. joshi_nitish

    1658 Points

  5. Arjun

    1294 Points

  6. Hemant Parihar

    1184 Points

  7. Arnab Bhadra

    1112 Points

  8. Shubhanshu

    1054 Points

  9. Ahwan

    900 Points

  10. rahul sharma 5

    706 Points


24,022 questions
30,966 answers
70,346 comments
29,342 users