Lab : Use recursion to nd the kth smallest number in an array You will write a program that allows the user to recursively nd the kth smallest element from an array. We have provided a Lab.java le with code to read in a data le of integers into an array of Integers and print the number of elements read in, N. Complete the recursive function kSmall which, given an argument k between 1 and N and an array of Comparable elements, returns the kth smallest element in the array. You also need to add a loop in the main method that repeatedly prompts the user to input an argument between 1 and N. The program should loop until an index less than 1 or greater than N is entered as the index. For a valid index, k, call kSmall to compute the kth smallest integer read in and then write out an appropriate message. Submit only the le Lab.java. We will use our own data les to test your work.

----------------------------------------------------------------------------

import java.util.Scanner; import java.io.IOException; import java.io.File; import java.util.Vector;

public class Lab{ /** * Partitions an array for quickSort. * @param first is the index of the first element to sort with * first <= last. * @param last is the index of the last element to sort with * first <= last. * @param theArray is the array to be sorted: the element * between first and last (with * first <= last)will be sorted. * @return the index of the pivot element of * theArray[first..last]. Upon completion of the method, this will * be the index value lastS1 such that S1 = * theArray[first..lastS1-1] < pivot theArray[lastS1] == pivot S2 = * theArray[lastS1+1..last] >= pivot */ private static > int partition(E[] theArray, int first, int last) { // tempItem is used to swap elements in the array E tempItem; E pivot = theArray[first]; // reference pivot // initially, everything but pivot is in unknown int lastS1 = first; // index of last item in S1 // move one item at a time until unknown region is empty for (int firstUnknown = first + 1; firstUnknown <= last; ++firstUnknown) { // Invariant: theArray[first+1..lastS1] < pivot // theArray[lastS1+1..firstUnknown-1] >= pivot // move item from unknown to proper region if (theArray[firstUnknown].compareTo(pivot) < 0) { // item from unknown belongs in S1 ++lastS1; tempItem = theArray[firstUnknown]; theArray[firstUnknown] = theArray[lastS1]; theArray[lastS1] = tempItem; } // end if // else item from unknown belongs in S2 } // end for // place pivot in proper position and mark its location tempItem = theArray[first]; theArray[first] = theArray[lastS1]; theArray[lastS1] = tempItem; return lastS1; } // end partition

public static > E kSmall(int k, E[] array, int first, int last){

/* TO COMPLETE */ }

public static void main(String[] args){ try{ Scanner console = new Scanner(System.in); System.out.println("Enter the name of the file containing the data"); String filename = console.next(); // read the data in the file Vector vec = new Vector(); Scanner scanData = new Scanner(new File(filename)); while(scanData.hasNext()) vec.add(scanData.nextInt()); scanData.close(); Integer[] myArray = new Integer[vec.size()]; int count=0; System.out.println("The integers in the file "+filename +" are: "); for (Integer val:vec){ myArray[count]=val; System.out.print(val+" "); count++; } /* TO COMPLETE */ // code to ask user for an index, k, between 1 and the number of integers read in, N // if number entered is outside the [1,N] range, exit loop // otherwise call ksmall to find the kth smallest element, write out the value with // an appropriate message, and loop for the next input } catch(IOException e){ System.err.println("IOError!!! " + e); System.exit(9); } } }//end class