In java, an quicksort algorithm was implemented along with an recurisve algorithm. Check to see if the quicksort algorithm is working correctly (todo: regions s1 and s2)

You are provided with a tester class.

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 quicksort algorithm

while (first <= last) {

//searching number which is greater than pivot, bottom up

while(theArray[first]< p) {

first++;

}

//searching number which is less than pivot, top down

while (theArray[last] > p) {

last--;

}

//swap the values

if (first <= last) {

int tmp = theArray[first];

theArray[first] = theArray[last];

theArray[last] = tmp;

//increment first index and decrement last index

first++;

last--;

}

}

return lastS1; // the index of the pivot element

}

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

int pivotIndex = partition(anArray, first, last);

int p = anArray[pivotIndex]; // p is the pivot

// ToDo: Return the kth smallest value in anArray[first..last].

// Refer to the recursive algorithm on page 151-152 of the textbook.

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; // Dummy return

} else if (k < left + 1) {

return kSmall(k, anArray, first, left - 1);

} else {

return kSmall(k,anArray,left + 1, last);

}

}

}

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);

// ToDo: Read input k and print out the k-th smallest item of the array.

// Note that your program should allow finding k-th smallest item from an array

// continuously (i.e., more than once) , refilling the array, and exiting the

// program when typing in "Q" or "q".

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.out.println("Thank you for using");

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 Elemnt : " + kthSmall);

}

}

while(choice!=null);

}

}