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

Actually what is meaning of SWAPPING:-

Assign the values

{

1. temp=a[i];

2.a[i]=a[j];

3. a[j]=temp;

}

---

in merge sort we assign the values to a temporary array frequently, but in a selection sort we assign values after one pass complete only.

---

Here swapping in merge sort comes in different way as at every level you need to move n elements that is also a swaping of values but by taking an extra array.

In merge sort brother you need to move n values everytime in new array and that thing happen for logn level...so nlogn movements you need.

But whereas in selection sort algo we do only 1 exchange only so for (n-1) elements max exchnge would be O(n-1)  i.e O(n) please refer algo if you cant get what i am saying you will get it easily.

---

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