Rewrite the quicksort algorithm using the partition in part b.

nontrivial e. Rewrite the QUICK SORT procedure to use HOARE-PARTITION 7-2 Quicksort with equal element values The analysis of the expected running time of randomized quicksort in Section 74.2 assumes that all element values are distinct. In this problem, we examine what happens when they are not a. Suppose that all element values are equal. What would be randomized quick- sort's running me in this case? h The PARTITION procedure returns an index q such that each element of A[P ..q _ l] is less than or equal to A[y] and each element of Ak +.r] is greater than Alq]. Modify the PARTITION procedure to produce a procedure PARTITION (A, p.r), which permutes the elements of Alp .r] and returns two indices q and t, where psqs r s T, such that all elements of Alg. ut] are equal, each element of Alp. q ]is less than Alyl, and each element of At t 1. .rl is greater than Alg Like PARTITION, your PARTITION procedure should take (r p) time c. Modify the RANDOMIZED QUICKSORT procedure to call PARTITION and name the new procedure RANDOMIZED-QUICKSORT Then modify the QUICKSORT procedure to produce a procedure QuicksORT (p) that calls e. Modity the RANDOMIZED-QuIckSORT procedure to call PAKTITION, and