/*
 * quicksort
 * copyright 2003 Burton Rosenberg. All rights reserved.
 * 12 september 2003
 * 15 september 2003
 *
*/

class QuickSort {

   static final boolean ASSERT = false ;

   static int 
   split( int [] a, int splitter, int bottom, int top ) {
     /* 
        modify a and return j such that
        a[i]<=splitter for i in [bottom,j)
        a[i]>splitter for  i in [j,top)
     */

     int l = bottom ;
     int u = top ;

     // LI, for i in [bottom,l), a[i]<=splitter
     //     for i in [u,top), a[i]>splitter

System.out.println("\nEnter split: bottom = "+bottom+", top= "+top+", split value= "+ splitter) ;
     while ( true ) {
printArray(a,bottom,top,l,u) ;
        while ( (l<u) && (a[l]<=splitter) ) l++ ;
        while ( (l<u) && (a[--u]>splitter) ) ;
        if ( l==u ) break ;
        swap( a, l++, u ) ;
        if ( ASSERT ) loop_invariant( a, splitter, bottom, l, u, top ) ;
     }
printArray(a,bottom,top,l,u) ;
     if ( ASSERT ) loop_invariant( a, splitter, bottom, l, u, top ) ;
System.out.println("Exit split: split at= "+l) ;
     return l ;
   }

   static void
   quicksort_aux( int [] a, int bottom, int top ) {


      if ( top-bottom < 2 ) return ;
      int k = split( a, a[bottom], bottom, top ) ;
      if ( k==top ) {
         // split did nothing
         swap( a, bottom, top-1 ) ;
         k = top - 1 ;
      }
      quicksort_aux( a, bottom, k ) ;
      quicksort_aux( a, k, top ) ;

   }

   static void
   quickSort( int [] a, int count ) {
printLegend() ;
      quicksort_aux( a, 0, count ) ;
   }


   // ----check loop invariant----

   static boolean
   loop_invariant( int [] a, int splitter, 
                   int bottom, int l, int u, int top ) {

     // LI, for i in [bottom,l), a[i]<=splitter
     //     for i in [u,top), a[i]>splitter

     boolean t = false ;
     while ( !t ) {
        for ( int i=bottom; i<l; i++ ) if ( a[i]>splitter ) break ;
        for (int i=u; i<top; i++ ) if ( a[i]<=splitter ) break ;
        t = true ;
     }
     System.out.println( "ASSERT: "+ t ) ;
     return t ;
   }

   // ----util----

   static void
   swap ( int [] a, int i, int j ) {
      int k = a[i] ; a[i] = a[j] ; a[j] = k ;
   }

   static void
   printArray( int [] a, int b, int t, int l, int u ) {
      for (int i=b; i<l; i++ ) 
          WriteHtml.pHTML_InColor("BLUE",a[i]+" ") ;
      for (int i=l; i<u; i++) 
          WriteHtml.pHTML_InColor("RED",a[i]+" ") ;
      for (int i=u; i<t; i++ )
          WriteHtml.pHTML_InColor("GREEN",a[i]+" ") ;
      System.out.println() ;
   }

   static void
   printLegend() {
      System.out.println("\nSplitter maintains an array section of smaller numbers") ;
      System.out.println("to the left, in blue, and a section of large numbers") ;
      System.out.println("to the right, in green. Unprocessed numbers in the middle are in red.") ;
   }

}

// eof