205 views

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.

retagged | 205 views
0

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.

0
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.
0
So, copying values in temporary array is a kind of Swapping.
0
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?
0
yes here its kind of that only than only selection sort is better...

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