[Solved] SOLVED:CIS 181: Object-Oriented Programming II Finding the K-th Smallest Item in an Array

Finding the K-th Smallest Item in an Array Objectives• To gain experience with using recursion by implementing the KSmall method.• To gain experience with using static methods by implementing the KthSmallest class.• To gain experience with implementing the Partition algorithm.• To learn how to test code by using the java.util.Random class to automatically generaterandom data.DescriptionYou will implement the class KthSmallest that consists of the following static methods:private static int partition(int[] theArray, int first, int last) (10pts)public static int kSmall(int k, int[] anArray, int first, int last) (10pts)The above class methods will be tested in the class KSmallTester. So, you are also asked tocomplete the main() method in the KSmallTester class for this purpose. Note that in Java, when aparameter passed to a method is an array, it is passed by reference. This means that the methodcan modify the contents of that array. For this reason, in class KSmallTester, we need to passarrayTmp, 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. Toget the deep copy of array, we can simply use a for-loop: for (int i=0; i<SIZE_OF_ARRAY; i++) arrayTmp[i] = array[i]; // Deep copy of the arrayNote: A deep copy implies duplicating the whole array or an object, so the deep copy and theoriginal copy are two independent data blocks. In constrast, a shallow copy is a reference copy,i.e., just a copy of the pointer to a shared data block. A Sample SolutionDownload the following jar file, and run it using the command “java -jar KSmallTester.jar” in acommand console (you can open a command console by clicking on Start – Run …, and type incmd).• KSmallTester.jarIf the file name is automatically changed into “KSmallTester.zip”, you need to change it back to“KSmallTester.jar”.Exercises1. Download the following class source files: KthSmallest.java KSmallTester.java2. In Eclipse, create a new Java project called “Project 1”, and import the above 2 files intopackage kSmall.3. Compile and run the program. Make sure it works (it prints out a random array).4. Implement the class called KthSmallest, which is specified as a public class without anyinstance 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 ofthese entries are smaller than p. theArray[lastS1] == p . S2 = theArray[lastS1 + 1 .. last] such that all of these entries are greaterthan 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 tolast.5. According to the given sample solution, complete the main method of the KSmallTesterclass to test the kSmall method defined in the KthSmallest class. The KSmallTester classshould support finding k-th smallest item from the same array more than once. It shouldalso 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, whenuser input is invalid, the system should not break. (10 pts)6. Test your program thoroughly with different data, and make sure your program runcorrectly. (If there are any bugs, it is suggested that you first thoroughly test the partitionmethod before testing the recursive method kSmall).7. Submit your completed program (KSmallTester.java and KthSmallest.java) tomyCourses.