1. Note this is a theoretical and programming assignment (non-collaborative problem) Given an array ali], , aj], with j- 1 > 2, let k = 1(it j)/2 and choose as the partition element for QUICKSORT the median among a[i], a[j], a[k] (i.e., the value that would be the middle if a [i], a [j] and a [k] were sorted). This is called median-of-three partitioning. (NOTE: There are several descriptions of the median-of-three methods in the web. Students should not seek solutions Online, rather students should meet the requirements as listed in this assignment) (c) [20 Points] What is the running time of QUICKSORT if you use median-of-three partitioning on an input set that is already sorted? Justify your answer. (d) [50 Points] Use QUICKSORT from the CLRS that uses a normal pivot process and the median-of- three process described above. Test your run time analysis of median-of-three, and then compare the average and worst case run times of QUICKSORT with the pivot processes. Note that you are allowed to use QUICKSORT from the CLRS code provided. Also, remember that CPU time is not a valid measure for testing runtime, instead, use something else such as the number of comparisons, estimated number of steps from code, etc. 1. Note this is a theoretical and programming assignment (non-collaborative problem) Given an array ali], , aj], with j- 1 > 2, let k = 1(it j)/2 and choose as the partition element for QUICKSORT the median among a[i], a[j], a[k] (i.e., the value that would be the middle if a [i], a [j] and a [k] were sorted). This is called median-of-three partitioning. (NOTE: There are several descriptions of the median-of-three methods in the web. Students should not seek solutions Online, rather students should meet the requirements as listed in this assignment) (c) [20 Points] What is the running time of QUICKSORT if you use median-of-three partitioning on an input set that is already sorted? Justify your answer. (d) [50 Points] Use QUICKSORT from the CLRS that uses a normal pivot process and the median-of- three process described above. Test your run time analysis of median-of-three, and then compare the average and worst case run times of QUICKSORT with the pivot processes. Note that you are allowed to use QUICKSORT from the CLRS code provided. Also, remember that CPU time is not a valid measure for testing runtime, instead, use something else such as the number of comparisons, estimated number of steps from code, etc