In Java, You will implement the class KthSmallest that consists of the following static methods: private static int partition(int[] theArray, int first, int last) (10 pts) public static int kSmall(int k, int[] anArray, int first, int last) (10 pts) The above class methods will be tested in the class KSmallTester. So, you are also asked to complete the main() method in the KSmallTester class for this purpose. Note that in Java, when a parameter passed to a method is an array, it is passed by reference. This means that the method can modify the contents of that array. For this reason, in class KSmallTester, we need to pass arrayTmp, which is a deep copy of array, to the class method KthSmallest.kSmall(k, arrayTmp, 0, SIZE_OF_ARRAY-1) as one of the parameters, so the original array can remain unchanged. To get the deep copy of array, we can simply use a for-loop: for (int i=0; i

1. Compile and run the program. Make sure it works (it prints out a random array).

2. Implement the class called KthSmallest, which is specified as a public class without any instance variables. The class KthSmallest defines the following static methods: private static int partition( int[] theArray, int first, int last) A method that partitions the array into the following sections: S1 is either empty or S1 = theArray[first .. lastS1 - 1] such that all of these entries are smaller than p. theArray[lastS1] == p . S2 = theArray[lastS1 + 1 .. last] such that all of these entries are greater than or equal to p. where p is the "pivot-value" defined by theArray[first]. public static int kSmall(int k, int[] theArray, int first, int last) A method that returns the k-th smallest of the portion of the array from first to last.

3. According to the given sample solution, complete the main method of the KSmallTester class to test the kSmall method defined in the KthSmallest class. The KSmallTester class should support finding k-th smallest item from the same array more than once. It should also support refilling new data into the array, so you can test the recursive method using a different array. Make sure your program is fail-safe for user inputs. In other words, when user input is invalid, the system should not break. (10 pts)

4.. Test your program thoroughly with different data, and make sure your program run correctly. (If there are any bugs, it is suggested that you first thoroughly test the partition method before testing the recursive method kSmall).

import java.util.*; public class KSmallTester { public final static int SIZE_OF_ARRAY = 10; public final static String PROMPT = "Please enter an integer k, 1<=k<=" + SIZE_OF_ARRAY + ", or 'R' to refill the array: "; public static void printArray(int[] array) { System.out.println(""); System.out.print("array = ["); for (int i=0; i < SIZE_OF_ARRAY-1; i++) System.out.print(""+ array[i]+" | "); System.out.println(""+ array[SIZE_OF_ARRAY-1]+"]"); System.out.println("-------------------------------------------------" + "-------------------"); } public static void randFillArray(int[] array) { Random random = new Random(); for (int i=0; i < SIZE_OF_ARRAY; i++) array[i] = random.nextInt(100); } public static void main(String argv[]) { int k = 1, kthSmallest = 0; int[] array = new int[SIZE_OF_ARRAY]; int[] arrayTmp = new int[SIZE_OF_ARRAY]; randFillArray(array); printArray(array); // ToDo: Read input k and print out the k-th smallest item of the array. // Note that your program should allow finding k-th smallest item from an array // continuously (i.e., more than once) , refilling the array, and exiting the // program when typing in "Q" or "q". } } 

public class KthSmallest { private static void swap(int[] theArray, int i, int j){ int temp = theArray[i]; theArray[i] = theArray[j]; theArray[j] = temp; } private static int partition(int[] theArray, int first, int last){ // Returns the index of the pivot element after partitioning // theArray[first..last] int p = theArray[first]; // use the first item of the array as the pivot (p) int lastS1 = first; // set S1 and S2 to empty // ToDo: Determine the regions S1 and S2 // Refer to the partition algorithm on page 495 of the textbook. return lastS1; // the index of the pivot element } public static int kSmall(int k, int[] anArray, int first, int last){ int pivotIndex = partition(anArray, first, last); int p = anArray[pivotIndex]; // p is the pivot // ToDo: Return the kth smallest value in anArray[first..last]. // Refer to the recursive algorithm on page 151-152 of the textbook. return p; // Dummy return } }