/*
 * @(#)QickSortAlgorithm.java	0.1 2008-07-17

 */

/**
 * A quick sort demonstration algorithm
 * QickSortAlgorithm.java
 *
 * @author yubo@yubo.org
 * @version 	@(#)QuickSortAlgorithm.java	0.1, 2008-07-17
 */

public class QuickSortAlgorithm extends SortAlgorithm
{

    /**
     * A version of pause() that makes it easier to ensure that we pause
     * exactly the right number of times.
     */
    private boolean pauseTrue(int lo, int hi) throws Exception {
	super.pause(lo, hi);
	return true;
    }


   void QuickSort(int a[], int lo, int hi) throws Exception
   {
	   /*
	    * lo~p~q~hi
	    */
      int p,q;
      if (lo >= hi ) return ;
      swap(a, lo, lo + (int)Math.random()*(hi - lo));
      p = lo;
      for ( q = lo + 1; q <= hi; q++)
    	  if (a[q] < a[lo]){
    		  swap(a, ++p, q);
    		  pauseTrue(lo,hi);
    	  }
      swap(a,lo,p);
      pauseTrue(lo,hi);
      QuickSort(a, lo, p-1);
      QuickSort(a, p+1, hi);
 
   }

   private void swap(int a[], int i, int j)
   {
      int T;
      T = a[i];
      a[i] = a[j];
      a[j] = T;
   }

   public void sort(int a[]) throws Exception
   {
      QuickSort(a, 0, a.length - 1);
   }
}