/**
    FILE:           QuickSort.java
    AUTHOR:         Cheng, Jeff
    LAST CHANGE:    3-22-02
    Functions:      QuickSort()--------> creates an array, may be presorted.
                    createAndSort()--> creates an array and sorts the
                                       array, may print array after.
                    print()----------> print the entire array.
                    sort()-----------> self-explanatory.
                    split()----------> split the array in two around
                                       a pivot.
                    
    COPYRIGHT:      You may use, modify, or distribute my code for 
                    non-commerical use only; you must cite me, Jeff Cheng, 
                    as the source. 
*/

package sorts;

class QuickSort{
    public static final int MAX_VALUE = 1000000;
    private int a[];
    
    public QuickSort(int arraySize, boolean presorted){
        a = new int[arraySize];
        
        if (presorted){  //  sorted array
            for (int i=0; i< a.length; i++){
                a[i] = i;
            }
        }
        else{
            //  seed the array elements randomly
            for (int i=0; i < a.length; i++){
                a[i] = (int)(Math.random()*MAX_VALUE);   
        }
        }
    }
    
    public static void createAndSort(int arraySize, boolean presorted,
                                     boolean printIt){
        long timeBegan = 0;
        long timeFinished = 0; 
        long timeNeeded = 0;
        
        //  create an array of integers;
        //  maybe sorted or unsorted to start with
        QuickSort aQuickSorter = new QuickSort(arraySize, presorted);

        //  time the sorting algorithm
        timeBegan = System.currentTimeMillis();
        
        aQuickSorter.sort();
        
        timeFinished = System.currentTimeMillis();
        timeNeeded = timeFinished - timeBegan;
        System.out.println("\t Sorting the array of size " + arraySize +
                            " took = " + timeNeeded + " milliseconds.");       
                            
        if (printIt){
            System.out.println("\n\t Now print the array elements:\n" +
                               "\t Note if the array is too large, " +
                               "the elements may run off the screen!\n");
            aQuickSorter.print();
        }
    }
    
  public void print(){
    for (int i = 0; i < a.length;i++){
        System.out.println(" a[" + i + "] = " + a[i] + "\n");
        }
 }
 
 public void sort(int a[], int first, int last) {
	if (first < last){
	    int pivot = split(a, first, last);
	    sort(a, first, pivot-1);  //  sort the lower half
	    sort(a, pivot+1, last); //  sort the higher half
	    }
    }

public void sort(){ //  used to hide call arguments in createAndSort()
    sort(a, 0, a.length-1);}
    
public int split(int a[], int first, int last){
    //  we are trying to split the array like so:
    //  a[ elements < pivot] || a[pivot] || a[elements > pivot]
    int lastSmallIndex = first;
    int temp = 0;
    
    for (int i = first + 1; i <= last; i++){
        if (a[i] < a[first]){
            //  if a smaller element is found, we extend the "small"
            //  region to the right and swap it with temp
            lastSmallIndex++;
            //  because we increment the region *before*
            //  swap(a[i], a[lastSmallIndex])
            //  the pivot point is left in its place, even if 
            //  a[1] is less than a[0] (or a[first]), because we
            //  have in that case, i == lastSmallIndex == 1;
            temp = a[i];
            a[i] = a[lastSmallIndex];
            a[lastSmallIndex] = temp;
            }
    }
    
    //  now the array has the small region and the large region,
    //  relative to the pivot that is.
    //  but remember that we are pivoting around the element, a[low]
    //  all we need to do now is swap the last element in the small
    //  region with the pivot element to create the following 3 parts:
    //  small region, pivot element, and large region.
    temp = a[first];  //  the rightful middle element
    a[first] = a[lastSmallIndex]; //  last element in small region
    a[lastSmallIndex] = temp;
    
    return lastSmallIndex;
    }
}