Reference no: EM131237668

Problem: Recall that quicksort selects an element as pivot, partitions an array around the pivot, and recurseson the left and on the right of the pivot. Consider an array that contains many duplicates andobserve that for such an array, quicksort recurses on all duplicates of the pivot element. In this taskyou are to develop a new partitioning procedure that works well on arrays with many duplicates.The idea is to partition the array into elements less than the pivot, equal to the pivot and greaterthan the pivot.

Required:

(a) Develop this idea into a partitioning algorithm and provide pseudocode. Make sureyour algorithm is in-place (i.e., do not use more than a constant amount of extra space).

(b) Use your partitioning algorithm to come up with a sorting algorithm. Analyze theworst-case running time of your algorithm.

(c) Find an array on which the original quicksort runs in time Θ(n2) but your algorithmfrom (b) in Θ(n).