Both merge sort and quick sort uses divide and conquer paradigm to sort unsorted list.

Question

(a) Imagine you want to write the quicksort algorithm to sort an array into non-increasing order. Write down the partition algorithm that is used in the divide phase in the quicksort algorithm. Show that the time complexity of this algorithm is 0 (n) .

(b) Identify the worst case situation in the naïve quicksort algorithm and show that in the worst case situation its time complexity is 0(n2)

Explanation

(a) Here we use two sorting methods and they are merge sort and quick sort

So as sometimes we need to arrange the number in the non-increasing form. At that time we have to place a greater number before pivot. And a smaller number after the pivot.

In this case, the algorithm for partition function will be:

• •  Set pivot= A[length], i=low-1, j=low
  •  Repeat steps 3 while j<=length-1
  •  If( A[j]<pivot)
    Set i=i+1
    Swap A[i] and A[j]
  •  Swap A[i+1] and A[length]
  •  Return i+1

(b) Giving us the recurrence tree as:

So here as we see there is not a binary tree formed by the numbers. Also, their complexity is then calculated by: n+ n+ n+…+n terms
Complexity = O(n2).

Also read, Write C++ statements to accomplish each of the following