// package insertsort;

/**
 * Title:
 * Description:
 * Copyright:    Copyright (c) 2001
 * Company:
 * @author
 * @version 1.0
 */

public class QuickSort
{

  static final boolean DEBUG=true ;

  public QuickSort() {
  }

  static void quickSort(int [] a, int len)
  {
    quickSortAux( a, 0, len ) ;
  }

  private static void quickSortAux(int [] a, int bottom, int top)
  {
     // precondition: a[i] for i in [bottom,top), numbers to sort

     if ( DEBUG ) printArray(a, bottom, top) ;

     if ( (top-bottom)<2 ) return ;

     int low = bottom ;
     int high = top ;
     int pivot = a[bottom] ;

     // L.I.: i in [bottom,low], a[i]<=pivot;
     //       i in (high, top), a[i]>pivot ;

     while (low<high)
     {
        // lower high until contradict L.I.
        while ( a[--high]>pivot ) ;
        // raise low until either meets high or contradicts L.I.
        while ( (low<high) && a[low]<=pivot ) low++ ;
        swap( a, low, high ) ;
     }
     if ( DEBUG ) if ( low!=high ) 
         System.out.println("Assert failed: low!=high") ;
     swap( a, bottom, low ) ;
     // postcond: a[low]==pivot; 
     //           a[i]<=pivot, bottom=<i<low; 
     //           a[i]>pivot, low<i<top;

     quickSortAux(a, bottom, low) ;
     quickSortAux(a, low+1, top) ;
  }

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

  static void printArray( int [] a, int i, int j )
  {
    System.out.println("PrintArray: [" + i + "," + j + ")") ;
    for (int k=i; k<j ; k++ )
       System.out.println(a[k]) ;
    System.out.println() ;
  }

}