Question

HW60.1. Array Quicksort You've done partition so now it's time to finish Quicksort. 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. To help you your parent class Partitioner provides a useful class method: 1. int partition (int[] values, int start, int end): this partitions values starting at start (inclusive) and ending at end (exclusive). It returns the position of the pivot value. Note that the test code will test that you call partition an appropriate number of times, so you should not call it on empty or single-item arrays. Also keep in mind that each partition does place the pivot value in the correct location. So if you start with { 2, 3, 0, 1 } and it is partitioned to { 0, 1, 3, 2 } only { 3, 2 } still needs to be partitioned, since 1 is the pivot and in the right place and o is a single-element array.

I currently have this but it doesn't work for the three item arrays

public class Quicksort extends Partitioner {
public static void quicksort(int[] values) {
if (values == null || values.length < 2) {
return;
}
quicksort(values, 0, values.length - 1);
}
private static void quicksort(int[] values, int start, int end) {
System.out.println(values);
System.out.println(start);
System.out.println(end);
if (values == null || Math.abs(start - end) == 1) {
return;
}
if (end > start) {
int pivotValueIndex = partition(values, start, end);
quicksort(values, start, pivotValueIndex - 1);
quicksort(values, pivotValueIndex + 1, end);
}
}
}

Answer 1

The sort function should be:

void sort(int values[], int start, int end)
{
if (start < end)
{
// get the partition index
int pi = partition(values, start, end);

// recursively sort the elements that lie on the left and
// the right part of the elements
sort(values, start, pi-1);
sort(values, pi+1, end);
}
}

void sort(int values[], int start, int end) if (start < end) // get the partition index int pi = partition (values, start, end); // recursively sort the elements that lie on the left and // the right part of the elements sort(values, start, pi-1); 'sort(values, pi+1, end); 10 11 12 13 14

If replacing this code still doesn't work then check whether the partition function's code is correct or not. The partition function's code looks like:

int partition(int values[], int start, int end)
{
int pivot = values[end];
int i = (start-1); // index of smaller element
for (int j=start; j<end; j++)
{
// If current element is smaller than the pivot
if (values[j] < pivot)
{
i++;

// swap values[i] and values[j]
int x = values[i];
values[i] = values[j];
values[j] = x;
}
}

// swap the value of the pivot with it's correct position
// i.e swap pivot with the element are ith index
int x = values[i+1];
values[i+1] = values[end];
values[end] = x;

return i+1;
}   

int partition(int values[], int start, int end), 18 19 int pivot = values[end]; int i = (start-1); // index of smaller elementi for (int j=start; j<end; j++) UAWNP // If current element is smaller than the pivot if (values[j] < pivot), { i++; // swap values[i] and values[j] int x = values[i]; values[i] = values[j]; values[j] = x; Nm mmmmmm mmm + // swap the value of the pivot with it's correct position // i.e swap pivot with the element are ith index int x = values[i+1]: values[i+1] = values [end]; values [end] = x; o 47 42 return i+1; 43

The full code for quick sort should look like this:

1 // Java program for implementation of quickSort 2 class quickSort - 3 { int partition(int values[], int start, int end), vouA w { int pivot = values[endl; int i = (start-1); for (int j=start; j<end; j++), 10 11 // If current element is smaller than the pivot if (values[j] < pivot), 12 13 i++; 17 // swap values[i] and values[j] int temp = values[i]; values[i] = values[i]; values[j] = temp; 18 19 20 21 // swap the value of the pivot with it's correct position // i.e swap pivot with the element are ith index int temp = values[i+1]; values[i+1] = values[end]; values[end] = temp; 25 27 return i+1; 28 29 30