/**
 *  <PRE>
 *  QuickSort.java
 *
 *  Revisions: 1.0 Nov. 04, 2002
 *               Created the QuickSort class
 *			   1.1 Nov. 09, 2002
 *				 Compiled, Finished, Commented
 *
 *  </PRE>
 *
 *	Collaboration Statement:
 *    I worked on the homework assignment alone, using only             
 *    course materials.
 *  
 *  Created with JCreatorLE, some indents are off when viewed through notepad
 *    or EMACS
 *
 *  @author <A HREF="mailto:gtg184g@mail.gatech.edu">Jose Manuel Caban</A>
 *  @version Version 1.1, Nov. 04, 2002
 */

public class QuickSort extends AbstractSort{

  ////////////////
  //Constructors//
  ////////////////
  
  /**
   *Constructor for QuickSort
   *@param arrayWrap, the array to be sorted
   */
  public QuickSort(ArrayWrapper arrayWrap){
    super(arrayWrap);
  }
	
  ///////////
  //Methods//
  ///////////
	
  /**
   *Sort the Array
   */
  public void doSort(){
    quickSort(0,arrayWrap.length()-1);
  }
  
  /**
   *Recursive quicksort
   */
  private void quickSort(int iStart, int iEnd){
  	/*
  	 *Algorithm uses some converted C++ code that I learned back
  	 *I originally learned this a little over a year ago
  	 *it may be similar to some code available over the net or other books
  	 *however, I have NO CLUE as to where it came from, as I said I learned 
  	 *it from my teacher and understand it fully
  	 */
  	
  	int iL=iStart, iR=iEnd;
  	Comparable cTemp;
    Comparable cPivot=arrayWrap.get((iStart+iEnd)/2);

	do
    {    
        for(;arrayWrap.get(iL).compareTo(cPivot)<0;iL++); 
        for(;arrayWrap.get(iR).compareTo(cPivot)>0;iR--);
        
        if (iL<=iR)
        {
            cTemp = arrayWrap.get(iL);
            arrayWrap.swap(iL,iR);
            arrayWrap.set(iR,cTemp);
            iL++;
            iR--;
        }
    }while(iL<=iR);

    if (iStart<iR){
    	quickSort(iStart, iR);
    }
    if (iL<iEnd){
    	quickSort(iL, iEnd);
    }
  }//end quickSort()
  
  /***********************************************************/  
    
  /**
   *  Debugging main for class QuickSort.  
   *  This method will rigorously test my code.
   *
   *  <br><br>
   *  @param args a String array of command line arguments.
   */
  public static void main(String[] args) {
    ArrayWrapper aw = new ArrayWrapper(ArrayWrapper.getRandomIntegerArray(40));    
    QuickSort qs = new QuickSort(aw);
       		    
    for(int i=0;i<aw.length();i++){
    	System.out.println(aw.get(i));
    }
    qs.doSort();
    System.out.println("\n/****Testing Now****/\n");
    for(int i=0;i<aw.length();i++){
    	System.out.println(aw.get(i));
	}
    
  }// end of main(String[] args)

}// end of class QuickSort