public class QuickSort{
  public static void main(String a[]){
    int i;
    int array[] = {12,9,4,99,120,1,3,10,13};
 
 
    System.out.println("Values Before the sort:\n");
    for(i = 0; i < array.length; i++)
      System.out.print( array[i]+"  ");
    System.out.println();
    quick_srt(array,0,array.length-1);
    System.out.print("Values after the sort:\n");
    for(i = 0; i <array.length; i++)
      System.out.print(array[i]+"  ");
    System.out.println();
    System.out.println("PAUSE");
  }
 
  public static void quick_srt(int array[],int low, int n){
    int swap;
 
	 int lo = low;
    int hi = n;
    if (lo >= n) {
      return;
    }
	 //Pivot median of three
    int mid = array[(lo + hi) / 2];
	 if(array[mid] < array[lo]){
	swap = array[lo];
	 array[lo]=array[mid];
	 array[mid]=swap;
	 }
	 if(array[hi] < array[lo]){
	 swap = array[lo];
	 array[lo]= array[hi];
	 array[hi]= swap;
	 }
	 if(array[mid] < array[lo]){
	 swap = array[mid];
	 array[mid]= array[hi];
	 array[hi] = swap;
	 }
	 swap = array[mid];
	 array[mid]= array[hi-1];
	 array[hi-1]= swap;
 
    while (lo < hi) {
      while (lo<hi && array[lo] < mid) {
        lo++;
      }
      while (lo<hi && array[hi] > mid) {
        hi--;
      }
      if (lo < hi) {
        int T = array[lo];
        array[lo] = array[hi];
        array[hi] = T;
      }
    }
    if (hi < lo) {
      int T = hi;
      hi = lo;
      lo = T;
    }
    quick_srt(array, low, lo);
    quick_srt(array, lo == low ? lo+1 : lo, n);
  }
}

public class QuickSort{
  public static void main(String a[]){
    int i;
    int array[] = {12,9,4,99,120,1,3,10,13};
 
 
    System.out.println("Values Before the sort:\n");
    for(i = 0; i < array.length; i++)
      System.out.print( array[i]+"  ");
    System.out.println();
    quick_srt(array,0,array.length-1);
    System.out.print("Values after the sort:\n");
    for(i = 0; i <array.length; i++)
      System.out.print(array[i]+"  ");
    System.out.println();
    System.out.println("PAUSE");
  }
 
  public static void quick_srt(int []k,int lb,int ub) {
      boolean flag=true;
      int i,j,key,temp;
 
      if(lb<ub)
         {
            i=lb;
            j=ub+1;
            key=k[lb];
            while(flag) {
                i++;
                while(k[i]<key && i<ub)
                    i++;
                j--;
                while(k[j]>key && j>lb)
                    j--;
                if(i<j) {
                    temp=k[i]; k[i]=k[j]; k[j]=temp;
                }
                else
                   flag=false;
            }
            temp=k[lb];
            k[lb]=k[j];
            k[j]=temp;
            quick_srt(k,lb,j-1);
            quick_srt(k,j+1,ub);
         }
  }
}