/*
 * QuickSort.java
 *
 * Created on August 11, 2003, 7:59 AM
 */

package qsort;

/**
 *
 * @author  dickey
 */
public class QuickSort_1 {
    
// Sort data[0..size-1]
    static void quickSort(int[] data) {
	qsort(data, 0, data.length-1);
}

// Sort data[lo..hi]
    static void qsort(int[] data, int lo, int hi) {
	// quit if empty partition
	if (lo >= hi) { return; }
	int pivotLocation = partition(data, lo, hi);	// partition array and return pivot loc
	qsort(data, lo, pivotLocation-1);
	qsort(data, pivotLocation+1, hi);
}

    //take lo to contain the pivot
    static int partition(int[] data, int lo, int hi) {
        int tempPivotindex = lo;
        int pivotVal = data[tempPivotindex];
        int left = lo+1;
        int right = hi;
        while (left <= right) {
            while (data[left] <= pivotVal && left <= hi) {
                left++;
            }
            while (data[right] > pivotVal && right > lo) {
                right--;
            }
            if (left < right) {
                int temp = data[left];
                data[left] = data[right];
                data[right] = temp;
            }
        }
        data[tempPivotindex] = data[right];
        data[right] = pivotVal;
        
        return right;
        
    }
    
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        
       int[] testArray = new int[] 
                    {1, 2, 0, -88, 9, 90, 19, 20, 29, -6};
       System.out.print("\n[before] "); printArray(testArray);
       quickSort(testArray);
       System.out.print("\n[after] "); printArray(testArray);
    }
    
    public static void printArray(int[] nums) {
        System.out.print("Array contents:");
        for (int n = 0; n < nums.length; n++) {
            if ((n%10) == 0) {
                System.out.println("");
            }
            System.out.print("  " + nums[n]);
        }
    }
    
}