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.

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

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

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.

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

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}

- All categories
- General Aptitude 1.6k
- Engineering Mathematics 7.3k
- Digital Logic 2.9k
- Programming & DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6k
- Compiler Design 2k
- Databases 4.1k
- CO & Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.4k
- Others 1.5k
- Admissions 592
- Exam Queries 577
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

49,456 questions

53,658 answers

186,156 comments

70,919 users