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 generate
random data.
Description
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<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 Solution
Download the following jar file, and run it using the command "java -jar KSmallTester.jar" in a
command console (you can open a command console by clicking on Start - Run ..., and type in
cmd).
• KSmallTester.jar
If the file name is automatically changed into "KSmallTester.zip", you need to change it back to
"KSmallTester.jar".
Exercises
1. Download the following class source files:
 KthSmallest.java
 KSmallTester.java
2. In Eclipse, create a new Java project called "Project 1", and import the above 2 files into
package 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 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.
5. 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)
6. 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).
7. Submit your completed program (KSmallTester.java and KthSmallest.java) to
myCourses.