contestada

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.

Respuesta :

temmydbrain

Answer:

Check the explanation

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

Otras preguntas