// QuickSort.java -- quick sort demo for cs 20
// cmc, 5/26/05

/** Implements a simple quick sort for integers. */
public class QuickSort extends IntSorter {

    /**
       Quick sort for integer array.
       @param a the array
    */
    public void sort(int a[]) {
        if (a.length < 2) return; // nothing to sort
        quicksort(a, 0, a.length-1); // initial call to quicksort method
    }

    // recursive quick sort for integer array
    private void quicksort(int a[], int left, int right) {
        if (left >= right) return; // nothing to sort

        // middle element chosen as pivot, and moved out of way to end
        int middle = (left + right) / 2;
        int pivot = a[middle];
        swap(a, middle, right);

        int i = left, j = right-1;
        while (i <= j) {
            // scan i from left, then j from right
            while (i <= j && a[i] <= pivot) i++;
            while (j >= i && a[j] >= pivot) j--;

            // swap values if scans haven't crossed yet
            if (i < j)
                swap(a, i, j);
        }

        // move pivot to proper position (i), and recursively sort both sides
        swap(a, i, right);
        print(a); // show intermediate result
        quicksort(a, left, i-1);
        quicksort(a, i+1, right);
    }
}