Question

Create a public non-final class named Partitioner. Implement a public static method int partition(int[] values) that returns the input array of ints partitioned using the last array value as the pivot. All values smaller than the pivot should precede it in the array, and all values larger than or equal to should follow it. Your function should return the position of the pivot value. If the array is null or empty you should return 0. You will probably want to review the array partitioning algorithm presented in class. Note that we are asking you to partition based on the last value in the array, rather than the first. However, you can address this difference with a small adjustment before you begin.

Answer 1

Check the explanation

Step-by-step explanation:

class Partioner {

public static int partition(int[] values) {

if (values == null || values.length < 1)

return 0;

// getting pivot value

int pivot = values[values.length - 1];

// pivot index

int pivot_index = values.length - 1;

// looping through values

for (int i = values.length - 2; i >= 0; i--) {

if (values[i] == pivot) {

pivot_index--;

continue;

}

// if immediate number is greater than pivot

if (values[i] > pivot) {

if (pivot_index - i == 1) {

int temp = values[i];

values[i] = pivot;

values[pivot_index] = temp;

pivot_index--;

} else {

int temp = values[i];

values[i] = values[pivot_index - 1];

values[pivot_index - 1] = temp;

temp = values[pivot_index - 1];

values[pivot_index] = temp;

values[pivot_index - 1] = pivot;

pivot_index--;

}

}

}

// returning pivot index

return pivot_index;

}

// testing the function

public static void main(String[] args) {

int values[] = { 11, 9, 2, 7, 21, 6, 10, 10, 10 };

System.out.println("pivot index : " + Partioner.partition(values));

System.out.println();

}

}

// OUTPUT

pivot index : 4