KSmall (find the k-th smallest element)

IMPORTANT: Read through the entire assignment write-up before starting to code your solution.

In this assignment you will:

solve a problem recursively and
continue to refresh yourself on elements of Java

Summary: You will implement a recursive method that returns the kth-smallest element of an array of integers. The algorithm you will implement recursively partitions an array, as described on pp. 148-152 of the text, until the partitioned element is in the kth position of the array (note: the kth element of a Java array is at index k-1).

The HW4 Class and the kSmall( ) method

Create a folder called HW4. For this assignment, as in the last lab, you should create a public static method in a class called HW4.java. You will run and test your kSmall method from the interactions pane initially, and later create a main method in a tester class to run the program (using the Run button.)

You will implement the following method:

public static int kSmall(int k, int[] anArray, int first, int last)

To implement your kSmall method, you will follow the algorithm given in the text at the end of Section 3.3, pp. 148-152. In particular, you should reread the end of Section 3.3 in the text, and be sure you understand the recursive solution described. The high level solution given proceeds as follows:

Select a pivot item in the array (to simplify things, you can always choose the first item at index 0 as the pivot.)
Partition the items in the array about the pivot item, selected in step 1.
Recursively apply the strategy to one of the partitions (because the kth smallest item will be in either one or the other.)

The challenging part will be figuring out how to do step 2, partitioning the items in the array around the pivot item. Paritioning the input array will involve swapping elements of the array in-place, meaning that you will be changing the contents of the array each time you partition it. A strategy for partitioning is given in the text on pages 493-500 and a somewhat simpler explanation is given on pages 150-151.

The kSmall algorithm is well-described in the text on pages 151-152, and should translate directly into recursive calls in your code. Remember that the whole array should be passed as an argument on each recursive call, along with indicies that specify the range of elements that are affected by that call.

We will discuss this assignment in detail on Tuesday, Sept 30, so don't despair if you find yourself stumped about how to proceed. Remember, we don't have lab on Oct 3, so you can use that time to finish the assignment (without coaching help from Sonia or me, but Leah should be on hand.)

Sample Output

When your kSmall() method is correctly implemented and tested in the interactions pane, create a TestHW4.java file in which you create arrays and test the results of using the kSmall method on those arrays. You should test at least 10 different arrays in your tester class (you may choose to generate the contents using a pseudo-random number generator.) The only method needed in the TestHW4 class is main. You do not need to instantiate any objects of type HW4 because you can call the kSmall method through the class name (HW4) exactly as you did in the interactions pane. You should create tests that produce output like that shown below (of course, you will have diferent random numbers...).

====================================================================
Array before calling kSmall(11, ...):
    [ -31  77 -46  15 -97  60 -64 -76  75 -71  92 -58 -31 -90 -54 ]
Array after calling kSmall(11, ...):
    [ -54 -46 -97 -64 -76 -71 -58 -31 -90 -31  15  60  77  75  92 ]
kth smallest number = 15

Notice that in the example above, the 11th smallest number is 15, and that the array after calling kSmall() is correctly partitioned around the location where 15 is stored.

Once you've run and verified that your kSmall() method is working properly, you are almost ready to submit your project.

Check your code documentation before submitting, making sure that you include header comments on each class and prior to method definitions. Be sure to explicitly state any pre-conditions affecting your methods and any post-conditions that are caused by the method. Make sure your code is properly indented and that there are no lines (including comment lines) longer than 80 columns.

Submitting your solution

Save both the HW4.java and TestHW4.java files in the HW4 folder. From a terminal window, type the following commands:

cd

cd cs125

submit125 HW4