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.

Answer 1

Answer:

See Explaination

Explanation:

public class Partitioner {

public static int partition(int[] values){

if(values==null || values.length==0)return 0;

// storing the pivot value

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

//sorting the array

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

int m_index = i;

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

if(values[j]<values[m_index])

m_index = j;

int tmp = values[m_index];

values[m_index] = values[i];

values[i] = tmp;

}

int i = 0;

// first finding the index of pivot

// value in sorted order and recording index in i

while (i<values.length){

if(pivot==values[i]){

if(i==values.length-1)break;

int j=0;

// finding the location for inserting the

while (j<values.length){

if(pivot<=values[j]){

// inserting the values

values[i] = values[j];

values[j] = pivot;

break;

}

j++;

}

break;

}

i++;

}

return i;

}

// main method for testing can be removable

public static void main(String[] args) {

int a[] = {4,1,6,2};

System.out.println(partition(a));

}// end of main

}