GeeksForGeeks Quiz

Question

Q) Consider a situation where swap operation is very costly.

Which of the following sorting algorithms should be preferred so that the number of swap operations are minimized in general?

(A) Heap Sort

(B) Selection Sort

(C) Insertion Sort

(D) Merge Sort

The Answer Given for This Question is (B). But My question is Why not (D) Since There is not a Single Swap operation is performed in Merge Sort.

Comments

So, copying values in temporary array is a kind of Swapping.

---

what About The Insertion Sort, In that We are moving the elements. That is Also A swapping ,means O(n^2) swapping in worst case?

---

yes here its kind of that only than only selection sort is better...

yes for insertion sort max O(n^2) max exchnages

Answer 1

In general , to minimise the number of swaps we use the selection sort bcoz everytime when we compare the elements of the array with the initial element we find the minimum element than the initial and do only one time swap it with the previous initial one.therefore the number of swaps is O(1) for every element and O(n) for n elements

whereas in merge sort there could be more than one swap at a time when we combine the two sorted arrays there could be possibility of getting more than one swap eg:{2,4,6} and {3,5,8}

Comments

Your mean during mergeing procedure we can get maximum swap??

---

no , not maximum. Because insertion do maximum swap as it insert element at last I think