/*
    DemoQuickSort2.java
    CIS 260
    David Klick
    2016-03-24

    This program demonstrates an iterative Quicksort that can handle 
    any data type implementing Comparable.
*/

public class DemoQuickSort2 {
    
    private static <T extends Comparable<? super T>> void quicksort(T[] ar) {
        int left, right, lptr, rptr;
        int leftSize, rightSize;
        
        java.util.Stack<Integer> stk = new java.util.Stack<>();
        stk.push(0);
        stk.push(ar.length-1);
        while (!stk.empty()) {
            right = rptr = stk.pop();
            left = lptr = stk.pop();
            
            // Randomize the data a little before partitioning
            int midpt = (lptr+rptr) / 2;
            T pivot = ar[midpt];
            ar[midpt] = ar[lptr];
            
            while (lptr < rptr) {
                while ((ar[rptr].compareTo(pivot) >= 0) && (lptr < rptr)) rptr--;
                if (lptr != rptr) ar[lptr++] = ar[rptr];
                while ((ar[lptr].compareTo(pivot) <= 0) && (lptr < rptr)) lptr++;
                if (lptr != rptr) ar[rptr--] = ar[lptr];
            }
            ar[lptr] = pivot;
            
            // Placing larger partition on stack first reduces max stack size
            leftSize = lptr - left;
            rightSize = right - left;
            if (leftSize < rightSize) {
                if (right > lptr+1) { stk.push(lptr+1); stk.push(right); }
                if (left < lptr-1) { stk.push(left); stk.push(lptr-1); }
            } else {
                if (left < lptr-1) { stk.push(left); stk.push(lptr-1); }
                if (right > lptr+1) { stk.push(lptr+1); stk.push(right); }
            }
        }
    }
    
    private static <T extends Comparable<? super T>> void display(T[] ar) {
        // Displays an int array with 8 columns per number
        for (T obj : ar) System.out.printf("%8s", obj.toString());
        System.out.println();
    }
    
    private static <T extends Comparable<? super T>> boolean isSorted(T[] ar) {
        // Returns true if array is in ascending order
        // Returns false if array is not in ascending order
        for (int pos=0; pos<ar.length-1; pos++) {
            if (ar[pos].compareTo(ar[pos+1]) > 0) return false;
        }
        return true;
    }
    
    public static void main(String[] args) {
        // Create an array of random integers
        Integer[] a = new Integer[10000000];
        java.util.Random rnd = new java.util.Random();
        for (int i=0; i< a.length; i++) a[i] = rnd.nextInt();
        
        // Display the unsorted array if not too large
        if (a.length <= 1000) display(a);
        System.out.printf("\nArray %s sorted%n", isSorted(a) ? "is" : "is not");
        
        // Sort the array
        System.out.println("\nSorting");
        quicksort(a);

        // Display the sorted array if not too large
        if (a.length <= 1000) display(a);
        System.out.printf("\nArray %s sorted%n", isSorted(a) ? "is" : "is not");
    }
}