15 points/ We have described a randomized algorithm for Selection) in class that runs in linear time. It turns out that there is a deterministic algorithm that has the same asymptotic performance. More pre- cisesly, there exists an algorithm Det-Selection(A, p,q, r) such that, given an array A, it returns the r-th smallest element in the subarray Alp,.,q] in time O(-p+1). For example, Det-Selection(A, p,q, 1) returns the smallest element in the subarray Alp,.,ql, while Det-Selection(A, p, q, 2) returns the sec- ond smallest element in the subarray Alp,...,q] Using this deterministic version of Selection procedure, give a deterministic version of the QuickSort algorithm that can sort an array in O(n log n) worst case running time. [Hint: Essentially, you need to choose the pivoting element in your Partition procedure more carefully. JYou can assume that all elements in the input array have distinct values. ] More specifically, you would need to provide pseudo-code for procedure Det-QuickSort(A,p, q) which sorts the subarray Alp,...,q] by a QuickSort like procedure (i.e, partition then recursive calls). You can use Det-Selection(A, p, q, r) as a sub-routine (i.e, you don't need to write its pseudo-code). To sort an array A, you will then call Det-QuickSort(A, 1,n) You also need to provide the worst case time complexity analysis of your algorithm. 15 points/ We have described a randomized algorithm for Selection) in class that runs in linear time. It turns out that there is a deterministic algorithm that has the same asymptotic performance. More pre- cisesly, there exists an algorithm Det-Selection(A, p,q, r) such that, given an array A, it returns the r-th smallest element in the subarray Alp,.,q] in time O(-p+1). For example, Det-Selection(A, p,q, 1) returns the smallest element in the subarray Alp,.,ql, while Det-Selection(A, p, q, 2) returns the sec- ond smallest element in the subarray Alp,...,q] Using this deterministic version of Selection procedure, give a deterministic version of the QuickSort algorithm that can sort an array in O(n log n) worst case running time. [Hint: Essentially, you need to choose the pivoting element in your Partition procedure more carefully. JYou can assume that all elements in the input array have distinct values. ] More specifically, you would need to provide pseudo-code for procedure Det-QuickSort(A,p, q) which sorts the subarray Alp,...,q] by a QuickSort like procedure (i.e, partition then recursive calls). You can use Det-Selection(A, p, q, r) as a sub-routine (i.e, you don't need to write its pseudo-code). To sort an array A, you will then call Det-QuickSort(A, 1,n) You also need to provide the worst case time complexity analysis of your algorithm