1. Write a method that implements Selection Sort.2. Write methods for two versions of Quick Sort, depending on how the pivot is chosen from each subarray to be sorted, as follows. (a) Choose the pivot from the first position of the subarray. (b) Choose three positions of the subarray at random and make the median of the values in these positions the pivot.3. Write a test 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.