// File QuickSort.java

public class QuickSort extends DivConqTemplate
{    
    protected boolean isSimple (Problem p)
    {   return ( ((QuickSortDesc)p).getFirst() >=
                 ((QuickSortDesc)p).getLast()     );
    }

    protected Solution simplySolve (Problem p)
    {   return (Solution) p ;   }
    
    protected Problem[] decompose (Problem p)
    {   int first = ((QuickSortDesc)p).getFirst();
        int last  = ((QuickSortDesc)p).getLast();
        int[] a   = ((QuickSortDesc)p).getArr ();
        int x     = a[first]; // pivot value
        int sp    = first;
        for (int i = first + 1; i <= last; i++)
        {   if (a[i] < x)
            {   swap (a, ++sp, i);   }
        }
        swap (a, first, sp);
        Problem[] ps = new QuickSortDesc[2];
        ps[0] = new QuickSortDesc(a, first, sp-1);
        ps[1] = new QuickSortDesc(a, sp+1, last);
        return ps;
    }
    
    protected Solution combine (Problem p, Solution[] ss)
    {   return (Solution) p;   }
    
    private void swap (int [] a, int first, int last)
    {   int temp = a[first];
        a[first] = a[last];
        a[last]  = temp;
    }
}

// File QuickSortDesc.java

public class QuickSortDesc implements Problem, Solution
{
    public QuickSortDesc (int[] arr, int first, int last) 
    {   this.arr   = arr;  
        this.first = first;
        this.last  = last;
    }
    public int[] getArr ()   { return arr;   }
    public int   getFirst () { return first; }
    public int   getLast ()  { return last;  }

    private int[] arr;
    private int   first;
    private int   last;
}

// File QuickSortDriver.java

public class QuickSortDriver
{
    public static void main (String[] args)
    {   QuickSort qs = new QuickSort();

        int[] sort10 = {10, 9, 1, 2, 8, 7, 5, 5, 3, 4};
        System.out.println("Unsorted:  " + printIntArr(sort10));
        qs.solve( new QuickSortDesc(sort10, 0, sort10.length-1) );
        System.out.println("Sorted:    " + printIntArr(sort10));
        System.out.println();

        int[] sortrev = {9, 8, 7, 5, 5, 4, 3, 2, 1};
        System.out.println("Unsorted:  " + printIntArr(sortrev));
        qs.solve( new QuickSortDesc(sortrev, 0, sortrev.length-1) );
        System.out.println("Sorted:    " + printIntArr(sortrev));
        System.out.println();

        int[] sorted = {1, 2, 3, 4, 5, 5, 7, 8, 9};
        System.out.println("Unsorted:  " + printIntArr(sorted));
        qs.solve( new QuickSortDesc(sorted, 0, sorted.length-1) );
        System.out.println("Sorted:    " + printIntArr(sorted));
        System.out.println();

        int[] sort01 = {1};
        System.out.println("Unsorted:  " + printIntArr(sort01));
        qs.solve( new QuickSortDesc(sort01, 0, sort01.length-1) );
        System.out.println("Sorted:    " + printIntArr(sort01));
        System.out.println();

        int[] sort00 = {};
        System.out.println("Unsorted:  " + printIntArr(sort00));
        qs.solve( new QuickSortDesc(sort00, 0, sort00.length-1) );
        System.out.println("Sorted:    " + printIntArr(sort00));
        System.out.println();
    }

    private static String printIntArr (int[] arr)
    {   if (arr.length == 0) 
        {   return "[]";   }
        String outstr = "[" + arr[0];
        int i = 1;
        for( ; i < arr.length-1; i++)
        {  outstr = outstr + "," + arr[i];   }
        return (outstr + "]");
    }
}