/*
 * @(#)SSortAlgorithm.java	0.1 08/07/18
 *
 */

/**
 * ΏμΛΩΡ‘Τρ
 * SSortAlgorithm.java
 *
 * @author yubo
 * @version 	@(#)SSortAlgorithm.java	0.1, 2008-07-18
 */
public class SSortAlgorithm 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 QuickSelect(int a[], int lo, int hi, int sel) throws Exception
   {
	   
	  /*
	    * lo~p~q~hi
	    */
      int p,q;
      p = lo;
      
      if (lo >= hi ){    	  
    	  pauseTrue(p,p);
    	  return ;
      }
    	  
      swap(a, lo, lo + (int)Math.random()*(hi - 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);
      if(sel + lo == p )  
    	  pauseTrue(p,p);
      if(sel + lo <  p )  QuickSelect(a, lo, p-1, sel);
      if(sel + lo >  p )  QuickSelect(a, p+1, hi, sel - (p+1-lo));
   }

   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[], int sel) throws Exception
   {
      QuickSelect(a, 0, a.length - 1, sel - 1);
   }
}