The Gateway to Computer Science Excellence
0 votes

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.

in Algorithms by Active
retagged by | 343 views

Actually what is meaning of SWAPPING:-

Assign the values


1. temp=a[i];


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 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

1 Answer

0 votes
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}
by Junior
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

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,218 questions
59,876 answers
118,119 users