812 views
1 votes
1 votes
I am not getting which algorithm has minimum no of swap operations , acc to me both selection and insertion should be at the lowest level as well as merge sort since after dividing the arrays we merely merge them where do we swap in that , please clarify this , I am a bit confused regarding counting the no of swap operations .

1 Answer

Best answer
3 votes
3 votes

In the worst case answer should be selection sort. Because we use a temp variable for finding the maximum value in each iteration and do a swap only once for the inner loop. In this way we swap only $ n$ times for the whole algorithm in any case. 

Think of it like sorting a structure containing multiple objects. So, swap operation is heavy. So, here selection sort makes sense. 

In insertion sort- for each element after finding its position we are shifting all elements to the right. These shifts can also be considered as swaps as they are swapping the positions. 

For merge sort we are using an auxiliary array and we can assume all elements are swapped. 

http://gatecse.in/wiki/Complexities_of_Basic_Sorting_Algorithms

selected by

Related questions

8 votes
8 votes
2 answers
1
1 votes
1 votes
1 answer
3
Purple asked Jan 27, 2016
24,669 views
If the number of records to be sorted is small, then ...... sorting can be efficient.A. MergeB. HeapC. InsertionD. Bubble
6 votes
6 votes
2 answers
4
radha gogia asked Jul 15, 2015
8,998 views
Assume that a CPU can process $10^8$ operations per second. Suppose you have to sort an array with $10^6$ elements. Which of the following is true? 1. Insertion sort will...