In Java, You will implement the class KthSmallest that consists of the following

Question

In Java, 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 array
Note: A deep copy implies duplicating the whole array or an object, so the deep copy and the
original 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.

1. Compile and run the program. Make sure it works (it prints out a random array).

2. 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.

3. 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)

4.. 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).

Explanation / Answer

KSmallTester .java

import java.util.*;

public class KSmallTester {

    public final static int SIZE_OF_ARRAY = 10;
    public final static String PROMPT = "Please enter an integer k, 1<=k<=" +
        SIZE_OF_ARRAY + ", or 'R' to refill the array: ";

    public static void printArray(int[] array) {

        System.out.println("");
        System.out.print("array = [");
        for (int i=0; i < SIZE_OF_ARRAY-1; i++)
            System.out.print(""+ array[i]+" | ");
        System.out.println(""+ array[SIZE_OF_ARRAY-1]+"]");
        System.out.println("-------------------------------------------------"
                         + "-------------------");
    }

    public static void randFillArray(int[] array) {
        Random random = new Random();

        for (int i=0; i < SIZE_OF_ARRAY; i++)
            array[i] = random.nextInt(100);
    }

    public static void main(String argv[]) {
        int k = 1, kthSmallest = 0;
        int[] array = new int[SIZE_OF_ARRAY];
        int[] arrayTmp = new int[SIZE_OF_ARRAY];

        randFillArray(array);
        printArray(array);

        String choice=null;
        Scanner sc=new Scanner(System.in);
      
        do
       {
           System.out.println(PROMPT);
           choice = sc.nextLine();

           if (choice.equalsIgnoreCase("R")) {
               randFillArray(array);
               printArray(array);
           } else if (choice.equalsIgnoreCase("q")) {
               System.exit(0);
           } else {
               int kth = Integer.parseInt(choice);
               // Create a deep copy of array
               for (int i = 0; i < SIZE_OF_ARRAY; i++) {
                   arrayTmp[i] = array[i];
               }

               int kthSmall = KthSmallest.kSmall(kth, arrayTmp, 0, SIZE_OF_ARRAY - 1);
               System.out.println("Kth Smallest Element : " + kthSmall);
           }

       }
        while(choice!=null);

    }

}

KthSmallest .java

public class KthSmallest {

    private static void swap(int[] theArray, int i, int j){
        int temp = theArray[i];
        theArray[i] = theArray[j];
        theArray[j] = temp;
    }

    private static int partition(int[] theArray, int first, int last){
    // Returns the index of the pivot element after partitioning
    // theArray[first..last]

        int p = theArray[first];    // use the first item of the array as the pivot (p)
        int lastS1 = first;         // set S1 and S2 to empty

        // ToDo: Determine the regions S1 and S2
        // Refer to the partition algorithm on page 495 of the textbook.

        return p;              // the index of the pivot element
      
        /****
         * I am using first element as pivot
         * please comlete this code as I don't know what is at page 495.
         */
    }

    public static int kSmall(int k, int[] anArray, int first, int last){
        int p = partition(anArray, first, last); // p is the pivot

       int left = first;
       int right = last;
   
       while (true) {
   
           while (anArray[left] < p && left < right) {
               left++;
           }
   
           while (anArray[right] >= p && right > left) {
               right--;
           }
   
           if (left == right) {
               break;
           }
   
           swap(anArray, left, right);
       }
   
       swap(anArray, left, last);
   
       if (k == left + 1) {
           return p;
       } else if (k < left + 1) {
           return kSmall(k, anArray, first, left - 1);
       } else {
           return kSmall(k, anArray, left + 1, last);
       }
    }
}

Output

array = [3 | 57 | 96 | 19 | 39 | 63 | 64 | 2 | 2 | 15]
--------------------------------------------------------------------
Please enter an integer k, 1<=k<=10, or 'R' to refill the array:
2
Kth Smallest Element : 2
Please enter an integer k, 1<=k<=10, or 'R' to refill the array:
R

array = [48 | 7 | 61 | 45 | 2 | 80 | 90 | 90 | 88 | 44]
--------------------------------------------------------------------
Please enter an integer k, 1<=k<=10, or 'R' to refill the array:
q

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.