Complete the implementation of the following class. public class Quicksort {publ
ID: 3581796 • Letter: C
Question
Complete the implementation of the following class. public class Quicksort {public static void quickSort (int[]list quickSort(list, 0, list.length-1);} private static void quicksort(int[] list, int first. int last) {if (last > first) {int pivotIndex - partition(list, first, last); quickSort(list, first, pivotIndex - 1); quickSort(list, pivotIndex + 1, last);}}/** Partition the array list [first.. last] */private static int partition(int(1 list, int first, int last) {int pivot = list [first];//Choose the first element as the pivot int low = first + 1;//Index for forward search int high = last;//Index for backward searchExplanation / Answer
Here is the code for you:
public class QuickSort
{
public static void quickSort(int[] list)
{
System.out.println(" Quick Sorting process"); // Displays a message to screen
quickSort(list, 0, list.length - 1); //Calling the function QuickSort with 3 parameters, first parameter being the name of the array, the second parameter being the lower bound of the array(0), the third parameter being the upper bound of the array(12) which means that is an array of 13 elements.
System.out.println(" Quick Sorting"); //Displays a message to screen
System.out.print("["); //Displays a message to screen
for(int i=0; i<list.length; i++) //Loop runs for 13 times, starting from 0 to 12.
{
System.out.print(" " + list[i]); //Displays all the elements in the array, of course in sorted order.
}
System.out.println("]"); //Displays a message to screen
}
private static void quickSort(int[] list, int first, int last) //This function actually sorts the array.
{
if(last > first)
{
int pivotIndex = partition(list, first, last);
quickSort(list, first, pivotIndex - 1);
quickSort(list, pivotIndex + 1, last);
}
}
/**Partition the array list[first..last]**/
private static int partition(int[] list, int first, int last)
{
int pivot = list[first]; //Choose the first element as the pivot.
int low = first + 1; //Index for forward search.
int high = last; //Index for backward search.
//Please keep in mind that, both the boundary pointers will move towards each other.
if (first >= last) //If we have no elements in the array.
{
return last; //Do nothing, and return.
}
int mid = list[(low + high) / 2]; //If not, consider the middle of the array value as pivot(mid).
while (low < high)
{ //Till both indexes didn't cross each other. As they move towards each other, they will eventually cross.
while (low<high && list[low] < pivot) //Till both the indexes didn't cross or you reach a number greater than pivot.
{
low++; //move the low index forward(towards the right).
}
while (low<high && list[high] > pivot) //Till both the indexes didn't cross or you reach a number less than pivot.
{
high--; //move the high index backwards(towards the left).
}
if(low < high) //if both the indexes didn't cross, (if you still have some more elements in the middle).
{
int T = list[low]; //Exchange the elements list[low] and list[high].
list[low] = list[high];
list[high] = T;
}
}
if (high < low)
{ //Once done with the loop, if the indexes cross over, exchange the index values.
int T = list[first];
list[first] = list[high];
list[high] = T;
}
return high;
}
}