In java, an quicksort algorithm was implemented along with an recurisve algorith
ID: 3734533 • Letter: I
Question
In java, an quicksort algorithm was implemented along with an recurisve algorithm. Check to see if the quicksort algorithm is working correctly, if not edit the code using the variables given to you(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);
}
}
Explanation / Answer
Here is your corrected code
/************************/
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){
int pivot = theArray[last];
int i = (first-1); // index of smaller element
for (int j=first; j<last; j++)
{
// If current element is smaller than or
// equal to pivot
if (theArray[j] <= pivot)
{
i++;
// swap arr[i] and arr[j]
int temp = theArray[i];
theArray[i] = theArray[j];
theArray[j] = temp;
}
}
// swap arr[i+1] and arr[high] (or pivot)
int temp = theArray[i+1];
theArray[i+1] = theArray[last];
theArray[last] = temp;
return i+1;
}
public static void quicksort(int anArray[], int first, int last)
{
if (first < last)
{
/* pi is partitioning index, arr[pi] is
now at right place */
int pivotIndex = partition(anArray, first, last);
// Recursively sort elements before
// partition and after partition
quicksort(anArray, first, pivotIndex-1);
quicksort(anArray, pivotIndex+1, last);
}
}
public static int kSmall(int k, int[] anArray, int first, int last){
quicksort(anArray, first, last);
return anArray[k-1];
}
}
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);
System.out.print("QuickSort : ");
for (int i = 0; i < SIZE_OF_ARRAY;i++) {
System.out.print(arrayTmp[i]+" ");
}
System.out.println(" ");
}
}
while(choice!=null);
}
}
/************************/output
tan@tan-X540LA:~/tanmay/java$ javac *.java
tan@tan-X540LA:~/tanmay/java$ java KSmallTester
array = [71 | 41 | 67 | 40 | 56 | 76 | 32 | 61 | 52 | 57]
--------------------------------------------------------------------
Please enter an integer k, 1<=k<=10, or 'R' to refill the array:
3
Kth Smallest Elemnt : 41
QuickSort : 32 40 41 52 56 57 61 67 71 76
Please enter an integer k, 1<=k<=10, or 'R' to refill the array:
2
Kth Smallest Elemnt : 40
QuickSort : 32 40 41 52 56 57 61 67 71 76
Please enter an integer k, 1<=k<=10, or 'R' to refill the array:
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.