Suppose you have a method triPartition whose documentation i

Suppose you have a method triPartition, whose documentation is given as follows:

/* triPartition: Given TWO pivots, pivot1 and pivot2,

* partition an unsorted list into THREE pieces.

*

* Details: Partition unsorted[start]...unsorted[end-1] into

* <--smalls--><pivot1><--mediums--><pivot2><--bigs-->

* where smalls = elements < pivot1 (in no particular order)

* = unsorted[start]...unsorted[pivot1Posn]

* mediums = elements < pivot2 and >= pivot1 (in no

* particular order).

* = unsorted[pivot1Posn+1]...unsorted[pivot2Posn]

* bigs = elements >= pivot2 (in no particular order)

* = unsorted[pivot2Posn+1]...unsorted[end-1]

* pivot1 is in its correct position in the sorted list

* = unsorted[pivot1Posn].

* pivot2 is in its correct position in the sorted list

* = unsorted[pivot2Posn].

* assumes: start + 2 <= end (unsorted has at least two elements)

* @param unsorted

* IN: Array unsorted contains the integers to be partitioned.

* pivot1 and pivot2 are already in unsorted[start] and

* unsorted[start+1] (note that pivot1 <= pivot2).

* OUT: unsorted is partitioned into

* <--smalls--><pivot1><--mediums--><pivot2><--BIGS-->

* @param start

* Index in unsorted defining the sublist to be partitioned.

* unsorted[start] ... unsorted[end-1] is to be partitioned.

* @param end

* Index in unsorted defining the sublist to be partitioned.

* unsorted[start] ... unsorted[end-1] is to be partitioned.

* @returns an object of type Pair, with two public (int) fields:

* - pivot1Posn : the position of pivot1

* - pivot2Posn : the position of pivot2

*/

The code for the Pair class is:

public class Pair {

public int pivot1Posn;

public int pivot2Posn;

}

QUESTION:

Write a recursive quicksort method that uses the method triPartition to sort an

array of ints. You may assume the existence of a swap method, if necessary.

Solution

public static void QuickSort_Recursive(int[] arr, int left, int right)

    {

        // For Recusrion

        if(left < right)

        {

            int pivot = Partition(arr, left, right);

            if(pivot > 1)

                QuickSort_Recursive(arr, left, pivot - 1);

            if(pivot + 1 < right)

                QuickSort_Recursive(arr, pivot + 1, right);

        }

    }

    public static void main(String[] args)

    {

        int[] numbers = { 3, 8, 7, 5, 2, 1, 9, 6, 4 };

        int len = 9;

            System.out.println(\"QuickSort By Recursive Method\");

        QuickSort_Recursive(numbers, 0, len - 1);

            for (int i = 0; i < 9; i++)

                  System.out.println(numbers[i]);

            System.out.println();

       

    }

}