made easy test series:algorithms,sorting

Question

why not merge sort?we don’t swap in merge sort,we just create auxillary arrays and merge them by changing elements in the original array.should we consider that as a swap?

Comments

this is the pseudocode for merge procedure from clrs book,I think swap(X,Y) moves the contents of X to Y and Y to X ,but here(in Lines 12-17) it just merges the contents of 2 arrays by editing the original array(A[k]=L[i]).why is this counted as swaping ,we have not moved the previous contents of A[k] to L[i];

---

@hitesh159

is it merging without swapping?

Without swapping we cannot get a sorted order

---

Yes answer should be selection sort as it is implements the descending priority queue as an unordered array.the number of interchange is always n-1.

Answer 1

For number of swaps in merge sort, see the pictures below. Recursive merge sort is used.

Comments

Answer will be option b.

In worst case,
1. No of swaps in merge sort= n*(n-1)/2

2. No of swaps in quick sort = n*(n-1)/2

3. No of swaps in bubble sort = n*(n-1)/2

4. No of swaps in selection sort= n-1

Answer 2

Just think about for 2 element array .and apply the merge sort .You can clearly see that there is a sawp between the 2 elements.

So yes merge sort also performs swap between elements .

No of swap in merge sort =O(N^2)

Answer 3

In selection sort the number of swaps is always O(n).

Why? We find minimum element in unsorted part of array and swap it with first element of unsorted part of array. So for each phase only 1 swap is there.

In Insertion Sort in worst case number of swaps is O($n^2$). For merge sort no of swap is $O(N^2)$

Answer 4

Firstly, they have not asked about the number of comparisons. They are asking about the swaps that will take place in sortings-

1. In quick sort total 0(n^2) swaps take place. i.e initially we have to find element from LHS to R.H.S. which is greater than pivot and then from R.H.S. to L.H.S. for element smaller than pivot. If found then swap and repeat and divide and repeat. 
2.  In selection sort find the minimum element and then swap with first element. Repeat and swap. Thus 0(n) swaps.
3. In merge sort first n/2 then n/2 then n/2…… total 0(nlogn) swaps
4. in bubble sort  0(n^2)  swaps take place.

Hence option B is correct

Comments

corrected...thanks brother:)

---

in merge sort its n2 or nlogn please let me sir

---

@avadh

Merge sort has a time complexity of O(n log n)...

It's easier to confirm this by closely inspecting the iterative implementation you've described. The algorithm scans the list log(n) times.

In your example, it merges every pair, then every four, then every eight, then all sixteen, bringing it to a total of 4 = log2(16) iterations.

Since the list itself is length n, the total time complexity is in the order of n log(n), which is validated by calculating that 64 elements in total are iterated by scanning a list of 16 items 4 times….

 

The fault in your analysis is incorrectly assuming that every merge is performed with a time complexity of O(n). The time complexity of each merge in a merge sort cannot trivially be represented in terms of n...