Question

Create a public non-final class named Quicksort that extends Partitioner. Implement a public static method void quicksort(int[] values) that sorts the input array of ints in ascending order. You will want this method to be recursive, with the base case being an array with zero or one value. You should sort the array in place, which is why your function is declared to return void. If the passed array is null you should just return. Your solution should also not make copies of the array as it runs.

Answer 1

Check the explanation

Step-by-step explanation:

Kindly Note that you did not mention any specific program language. So, the answer was written in Java language.

Text format code:

//Create a main class, QuickSortDemo

public class QuickSortDemo

{

//Method definition of quicksort with a parameter

public static void quicksort(int[] values)

{

quicksort(values, 0, values.length - 1);

}

//Method definition of quicksort with multiple parameters

private static void quicksort(int[] values, int start, int end)

{

if (end > start)

{

int pivotValueIndex = partition(values, start, end);

//Call recursion method

quicksort(values, start, pivotValueIndex - 1);

quicksort(values, pivotValueIndex + 1, end);

}

}

//Method definition of partition

private static int partition(int[] values, int start, int end)

{

int pivotValue = values[start];

int last = start + 1;

int first = end;

while (first > last)

{

while (last <= first && values[last] <= pivotValue)

last++;

while (last <= first && values[first] > pivotValue)

first--;

if (first > last) {

int temp = values[first];

values[first] = values[last];

values[last] = temp;

}

}

while (first > start && values[first] >= pivotValue)

first--;

if (pivotValue > values[first])

{

values[start] = values[first];

values[first] = pivotValue;

return first;

}

else

{

return start;

}

}

//main method

public static void main(String[] args)

{

int[] values = {2,3,0,1};

//Display input data

System.out.print("Input values:{");

for (int i = 0; i < values.length; i++)

{

System.out.print(values[i]);

if(i < values.length - 1)

System.out.print(", ");

}

System.out.print("}");

//Call the method

quicksort(values);

//Display output values

System.out.print("\\After partition, then the "

+ "result in ascending order:{");

for (int i = 0; i < values.length; i++)

{

System.out.print(values[i]);

if(i < values.length - 1)

System.out.print(", ");

}

System.out.print("}");

}

}

OUTPUT: