Java version!

Quick Sort is a popular sorting algorithm because it usually achieves optimal O(n log n) running time in practice. However, in the worst case, the running time can be quadratic. The method to choose the pivot is crucial to avoid the worst cases. The purpose of this homework is to evaluate experimentally the performance of Quick Sort for different methods of choosing the pivot, and compare with Selection Sort, which is simpler but quadratic. Write a method that implements Selection Sort. Write methods for two versions of Quick Sort, depending on how the pivot is chosen from each subaray to be sorted, as follows. Choose the pivot from the first position of the subarray. Choose three positions of the siibarrav at random and make the median of the values in these positions the pivot. Write attest program that measures the running time of the above three methods while sorting 1000000 numbers (adjust the quantity if needed). Use three types of inputs: already sorted in increasing order, already sorted in decreasing order, and an input with the numbers generated at random. Fill in the following chart with the running times observed. Draw conclusions from the values observed. Are the measureme significantly different for some cases ? why? How the pivot choice helps for those cases where the running time is smaller