import java.lang.*;
import java.util.*;
/** Simple Quick Sort
@author Dick Botting
@version 3.0
<p>
This sorts arrays of Strings..generic.  However it is designed to
be used to sort other objects after some systematic changes are
made in the code.
<p>
It also includes a main, test, and debug methods
that can be removed once you have tested your version
*/
class QSortable {
/* if you find the occurences of int that are flagged with the comment: generic
and change them to another type or class
and change the body of method lessThan
to compare your objects the algorithm should still work.
*/

/** The sorting criterion. if lessThan(a,b) then a should be before b
	in a correctly sorted list.
    You can replace the body to carry out a different sort. This
    function must follow the rules for a linear or total order if
    the sort routine is going to work correctly.
*/
   public static boolean /*generic*/ lessThan(String/*generic*/ x, String/*generic*/ y)
	{return x.compareTo( y ) < 0 ;}

   private String/*generic*/ list[];

/** Creates a list of n undefined items.
*/
   public QSortable(int n){ list = new String/*generic*/[n]; }

/** Main program designed to test the package
*/
   public static void main(String argv[]){
	test1(argv);
    }//main

   private static void test1(String argv[]){
	QSortable tester = new QSortable(9);
	tester.list[0]="The";
	tester.list[1]="quick";
	tester.list[2]="brown";
	tester.list[3]="fox";
	tester.list[4]="jumps";
	tester.list[5]="over";
	tester.list[6]="the";
	tester.list[7]="lazy";
	tester.list[8]="dog";

	tester.debug();
	tester.quicksort();
	tester.debug();

    }//test1

    private void debug(){
	System.out.println("-------");
	for(int i=0; i<list.length; i++){
		System.out.println( list[i] );
	}//for
	System.out.println("-------");
	System.out.println("");
    }//debug

/** Useful method: Exchange list[i] with list[j].
   <p>Disclaimer: will not work if list is not properly defined or i and j are not valid indexes for the list, or if the objects can not be assigned.
   <br>Contract: The new ith element is the old jth and vice versa.
   <br>No other elements in the array are effected.
   <br>The values in list will be the same as before, but permuted.
*/
   public void swap(int i, int j){
	String/*generic*/ t=list[i]; list[i]=list[j]; list[j]=t; return;
	}//swap
/**
   Useful method: Put list[i] and list[j] into order.
   <p>Disclaimer: will not work if list is not properly defined or i and j are not valid indexes for the list, or if the objects can not be assigned or comapared.
   <br>Contract: Afterwards lessThan( list[i], list[j] ) is true.
   <br>No other elements in the array are effected.
   <br>The values in list will be the same as before, but permuted.
*/
   public void sort2(int i, int j){ 
	if( ! lessThan( list[i], list[j])) swap(i,j); return;
	}//sort2

/** Put complete list into order.
   <p>Disclaimer: Will not work if list is not properly defined.
   <br>Contract: Afterwards the elements will be in increasing oder.
   <br>The values in list will be the same as before, but permuted.
   <br>Depends on: Calls quicksort(int,int);
*/
   public void quicksort( ) {quicksort(0, list.length-1);}

/** Sort first n elements of list.
   <p>Disclaimer: Will not work if list[0..n-1] are not properly defined.
   <br>Contract: Afterwards the elements 0..n-1 will be in increasing oder.
    <br>The values in the whole list will be that same as before, but 
	those between 0 and n-1 inclusive will be permuted.
   <br>Depends on: Calls quicksort(int,int);
*/
   public void quicksort( int n ) {quicksort(0,n-1);}


/** Sort i0'th thru j0th elements of list
   <p>Disclaimer: Will not work if list[i0..j0] are not properly defined.
   <br>Contract: Afterwards the elements i0..j0 will be in increasing oder.
    <br>The elements in the whole array will be that same as before, but 
	those between i0 and j0 inclusive may be permuted.
    <br>Algorithm:  Tony Hoare's famous quicksort.
    <br>Timing: for n items, 
	on average time is of order n*log(n), but
	the rare worst case is of order n*n.  It is best used on
	arrays that are highly disordered.
     <br> Space: Typically proportional to log(n), worst case proportional to n.
    <br>Depends on: calls method pivot().
*/
public void quicksort(int i0, int j0)/* sorts list[i0..j0] */
{
   /*final*/ int n=j0+1-i0; // number of items to be sorted
   int ip, i,j,k; // pivot point, and other subsripts
/* Analysis
   We can sort small arrays quickly:
      0 and 1 items are already sorted
      2 items may just need swapping
      3 items are handled well by 3 sorts of 2 items
   For a large number of items we use a "divide and conquer"
   strategy... cut the data into smaller parts, sort the parts,
   and reassemble the parts.

   If we could split the array
   into two parts so that the items in the left part where all
   less than those in the other part and then sorted each part
   on its own.   Reassembly would be trivial.

   Since this doesn't happen by luck we instead permute the
   list so that for some index ip and p, list[ip]==p.
   and
            [...less than p ... |  p  | ... greater than p ...]
             0              ip-1   ip   ip+1               n-1

   ip is called the pivot point, and p the pivot value.

   We choose a pivot value and reorder the array so that all the items
   less than the pivot are before the pivot value and all
   the items after the pivot are greater than the pivot.

*/
	//debug();

   if(n<=1) return;
   if(n==2) {sort2(i0,i0+1); return;}
   if(n==3) {sort2(i0,i0+1); sort2(i0+1,i0+2); sort2(i0,i0+1);return;}
   /*else n>3 */

   ip=pivot(i0, j0);
	   /* Here list[i0..ip-1]<=list[ip]<list[ip+1..j0] */
	//debug();
   quicksort(i0, ip-1); 
   quicksort(ip+1, j0);

	//debug();
}//quicksort

/**  Pivot the list about some value
   <p>Pre: list[i0..j0] is defined and i0<j0.
   <br>Post: Permutes list[i0..j0] but leaves rest of list unchanged
@return ip where list[i0..ip-1]<=list[ip]<list[ip+1..j0].
*/
private int pivot(int i0,int j0)
{
/* Pivotting can be done in several ways.  They are all
   clever, but this is the one that is easiest to get right.
   It was invented by Lomuto.
*/
   String/*generic*/ p;  //will become the pivot value.
   /*final*/ int n=j0+1-i0; //number items to be pivotted

   int ip;/*will become index of pivot*/
   int unseen=i0+1; /* index of items not yet pivotted */

   sort2(i0,i0+1); sort2(i0+1,i0+2); sort2(i0+1,i0); p=list[i0];
   /*  The above puts the first three items out of order.
       The first item is now out of the way of the action.
      list[i0..]={ p , <=p , >=p , ...}
                  i0  i0+1  i0+2   ...
   */

  /* initialize the pivot scan */
   ip=i0+1; 
   unseen=i0+2; 
      /*
      list[i0..j0]={ p , <=p , >=p , ... , ?? }
                    i0   ip   unseen ...     j0
      So  list[i0+1..ip]<= p >= list[unseen] and ip+1==unseen
      */

   /*skip past initial string of items <= p...*/
   while(unseen < j0 && lessThan(list[unseen], p) ) { 
      unseen++;
      ip++;
   }/* unseen==j0 or list[unseen]>p*/

      /*  list[i0+1..ip]<= p < list[ip+1] and ip+1==unseen
      and list[unseen-1] < list[unseen]
        or unseen==j0
      */
   unseen++;
      /*  list[i0+1..ip]<= p < list[ip+1..unseen-1] 
          or  unseen>j0 */

   while( unseen <=j0 ){ /*  list[i0..ip-1]<= p <list[ip+1..unseen-1] */

      if(lessThan(list[unseen], p)){ 
		   /* { p | items <= p | items > p | <=p | ???  }
		    *  i0 |+1        ip|ip+1        unseen     j0 
		    */
        swap(ip+1,unseen);
		   /* { p | items <= p | <=p | items > p |  ???  }
		    *  i0 |+1        ip|ip+1        unseen     j0 
		    */
        ip++;
		   /* { p | items <= p | <=p | items > p |  ???  }
		    *  i0 |+1            ip  |ip+1  unseen     j0
		    */
      }//end if 
		  /* else list[unseen]>p and so 
		   * { p | items <= p | items > p | > p | ???  }
		   * { p | items <= p |     items > p   | ???  }
		   *  i0 |+1      ip  |ip+1       unseen     j0
		   */

            /* list[i0+1..ip] are all <= p and p < list[ip+1..unseen] */
        unseen++;
            /* list[i0+1..ip] are all <= p and p < list[ip+1..unseen-1] */
   }//end while(unseen <=j0)

   /* here unseen==j0+1, so all elements have been seen and put in place
			except the pivot itself */

	      /* list[i0..ip] are all <= p and p < list[ip+1..j0] */
   swap(i0,ip);
	      /* list[i0..ip-1]<=list[ip]<list[ip+1..j0]*/
   return ip;
}//pivot

}//QSortable/*generic*/