CS 223 Out-lab 2
Week of 1/30

Due: to TA by 2/9

Fast Selection

The goal of this out-lab is to implement the linear time selection algorithm (see page 189 of CLRS). 

You should write a Selection class that implements a static method called select that has the following syntax:

public static int select(int[] array, int startIndex, int endIndex, int position)

Here array is an integer array.  The part of this array that we want to look at starts at startIndex and ends at endIndex.  Among these elements we want to find the one that has rank equal to position.

Hints

• You may find it helpful to use the method
  public static void sort(int[] a, int fromIndex, int toIndex)
  from the class java.util.Arrays to sort each consecutive group of five elements. 
• You can also use the partition function from class (modified to not reselect a pivot)
• You only need to make recursive call if the range of the array you are selected from has more than 5 elements.

Your code should include the following:

• a class called Selection.  This class should implement the static selection method described above.  This algorithm is very elegant and won't require that much code. 
   
• a driver class.  This class should first create a randomly ordered int array of size 100.  Call your selection method three times to find the elements with ranks 1, 5, and 20 respectively.  Then use the Arrays.sort method to sort your original array and print it out with line numbers.  The elements found by your selection algorithm should agree with the sorted list in the positions specified.

What to Turn In

• a printed copy of all source code.  Ensure the source code is documented.
• a printout of a test run of the driver.