I. Overview:

you will write a program to return the kth smallest element of an array A[] with n elements. (For example, k=1 is the smallest, k=n is the largest, and k=n/2 is the median.) In this programming assignment, you are to use two different algorithms, as describe below, to implement the solutions. 1.Algorithm1: Sort the array using QuickSort and pick the kth smallest element. This has average time complexity of O(nlogn) and worst-case time of O(n^2). 2.Algorithm2: Use Quick-Select (with LomutoPartition) discussed in our lecture (also available in the textbook). This algorithm has an average time complexity of O(n) and a worst-case time of O(n^2).

II. Requirements:

1.Run experiments for the following values of n: 10,000, 100,000 and 1,000,000. For each value of n, produce an array of randomly generated elements (you may use integers). Then use each of the two methods to find the kth smallest element for k=n/2 and print one line result: 2.Algorithm X: n, k, A[k], Number of Key-Comparisons Make sure that the same original array of n elements is used for both methods. Explain how the results compare with the expected analytical results. 3.Write all your own code. Do not use "off the shelf" code from any source. In particular, you are not allowed to use any sorting function from C/Java libraries. The only variable types allowed in your program are int and int[]. You are not allowed to use any reference data type in Java, like List, Set, etc. The function signature would look like: 4.select1(int[] a, int n, int k); Hint: Do not perform the key comparisons in-line. Rather, use a function to perform each key comparison, while incrementing a counter. 5.Your program should be written in either Java or C programming language.