/*
*
* $Author: work $
* $Revision: 1.9 $
* $Log: QuickSort.java,v $
* Revision 1.9  2000-03-30 22:50:54-06  work
* Changed invocation method.  No longer
* a static method only class to be invoked
* with QuickSort.sort(A,i,j) but with
* new QuickSort( A, i, j ) with immediately
* discarded object.  This way is more elegant
* and also thread-safe to boot.
*
* Revision 1.8  2000-03-30 22:33:05-06  work
* minor optimization of moving local temp
* variable in swap() to a static var in
* the embodying class
*
* Revision 1.7  2000-03-30 22:27:41-06  work
* removed debug statements
* non-randomized median-of-3 production release
*
* Revision 1.6  2000-03-30 22:23:44-06  work
* fixed subtle operator precedence bug:
* a + b >> 1 evaluates to (a + b) >> 1
* not a + (b >> 1) which is what we want
*
* debug statements still here
*
* Revision 1.5  2000-03-30 22:07:45-06  work
* draft completed, now to test
*
* Revision 1.4  2000-03-30 22:01:46-06  work
* use median-of-3 partitioning
* -- undecided whether to remove a variable (j)
* at the cost of readability
*
* Revision 1.3  2000-03-30 04:16:58-06  work
* fixed subtle bug in get random integer
* to choose pivot element
*
* Revision 1.2  2000-03-30 03:21:30-06  work
* debug version
*
* Revision 1.1  2000-03-29 23:23:36-06  work
* Initial revision
*
*/

/*
* Copyright (C) 2000  
*
*    This program is free software; you can redistribute it and/or modify
*    it under the terms of the GNU General Public License as published by
*    the Free Software Foundation; either version 2 of the License, or
*    (at your option) any later version.
*
*    This program is distributed in the hope that it will be useful,
*    but WITHOUT ANY WARRANTY; without even the implied warranty of
*    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
*    GNU General Public License for more details. 
*
*    You should have received a copy of the GNU General Public License
*    along with this program; if not, write to the Free Software
*    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
*/


import java.util.*;
import java.io.*;

final class SortableInteger extends SortableObject
{
	int x;
	
	SortableInteger( int n )
	{ x = n; }
	
	boolean greaterThan( SortableObject y )
	{ return x>((SortableInteger) y).x; }
	public String toString()
	{ return Integer.toString(x); }
}

final class QuickSort
{
	private SortableObject[] A;
	private SortableObject temp;
	
	public QuickSort( SortableObject[] arr )
	{ A = arr; sort( 0, A.length-1 ); }
	
	private void swap( int i, int j )
	{
		// System.out.println( "s: "+i+" "+j );
		temp = A[i];
		A[i] = A[j];
		A[j] = temp;
	}
	
	private void sort( int p, int r )
	{
		int q;
		
		while( p < r ) {
			// System.out.println( "e: "+p+" "+r );
			
			q = p + ((r-p) >> 1);
			
			// first compare
			if( A[p].greaterThan(A[q]) )
				swap( p, q );
			// second compare
			// A[r] now greater than either A[p], A[q]
			if( A[q].greaterThan(A[r]) )
				swap( q, r );
			// third is identical to first compare
			if( A[p].greaterThan(A[q]) )
				swap( p, q );
			
			// pivot = median of 3
			SortableObject pivot = A[q];
			
			{
				int i=p; q=r;
				do {
					do i++;
					while( pivot.greaterThan(A[i]) );
					do q--;
					while( A[q].greaterThan(pivot) );
					
					if( i < q ) swap( i, q );
					else break;
				} while( true );
				
				// pivot value equals A[i] and A[q]
				// so bump q back so that [p,q] is left part, [q+1,r] is right
				// This way, q is always < r, so no infinite recursion
				if( i == q )
					q--;
			}
			
			if( q-p+1 <= r-q ) {
				// left side at most as large as right so recurse on it				
				// System.out.println( "l: "+p+" "+q+" "+r );
				if( p < q ) sort( p, q );
				p = q + 1;
			} else {
				// otherwise right is smaller so recurse on it
				// System.out.println( "r: "+p+" "+q+" "+r );
				if( q+1 < r ) sort( q+1, r );
				r = q;
			}
		}
	}
	
	public static void main( String[] args )
	{
		int n=30;
		Random rand = new Random();
		
		SortableInteger[] A = new SortableInteger[n];
		
		for( int i=0; i<n; i++ ) {
			A[i] = new SortableInteger(rand.nextInt());
			System.out.print( A[i]+"\t" );
			if( (i+1)%5 == 0 ) System.out.println();
		}
		System.out.println();
		
		/*
		n = 4;
		A = new SortableInteger[n];
		for( int i=0; i<n; i++ ) 
			A[i] = new SortableInteger(-i);
		*/
		
		new QuickSort( A );
		
		for( int i=0; i<n; i++ ) {
			System.out.print( A[i]+"\t" );
			if( (i+1)%5 == 0 ) System.out.println();
		}		
	}
}