Quick3.java

public class Quick3 {

   private static void swap (int [] data, int i, int j) {
      final int temp = data[i];
      data[i]=data[j];
      data[j]=temp;
   }

   public static void quick_sort (int [] data, int n) {
      quick_sort (data, 0, n);
   }
      
   public static void quick_sort (int [] data, int first, int n) {
      if (n>2) {
	 final int pivot_index = partition (data, first, n);
	 final int n1 = pivot_index - first;
	 final int n2 = n-n1-1;

	 quick_sort (data, first, n1);         // Sort data[first..pivot_index-1], len=n1
	 //  data[pivot_index] = pivot value
	 quick_sort (data, pivot_index+1, n2); // Sort data[pivot_index+1..first+n-1], len=n2
      } else if (n>1) {
	 // Sort two elements
	 if (data[first+1]<data[first]) swap (data, first, first+1);
      }
   }

   /*
     Assume n>=3!  Median of three
     paritition data[first..first+n-1] into values <= data[first] and > data[first]
   */

   public static int partition (int [] data, int first, int n) {
      final int middle = first + (int) (n/2);
      final int last = first+n-1;
      if (data[middle]<data[first]) swap (data, first, middle);
      if (data[last]<data[first]) swap (data, first, last);
      if (data[last]<data[middle]) swap (data, middle, last);

      final int pivot = data[middle];

      // Place pivot at index last-1
      swap (data, middle, last-1);

      int i,j;
      for (i=first, j=last-1; ; ) {
	 while (data[++i]<pivot) ;
	 while (pivot<data[--j]) ;
	 if (i<j) {
	    swap (data,i,j);
	 } else {
	    break;
	 }
      }
      // Move the pivot element to its correct position at data[tooSmallIndex]
      data[last-1] = data[i];
      data[i] = pivot;

      return i;  // index of pivot
   }

   private static void printArray (int [] data, int n) {
      printArray (data, 0, n);
   }

   private static void printArray (int [] data, int first, int n) {
      System.out.print ("[");
      for (int i=first; i<first+n; i++) {
	 System.out.print (data[i]);
	 if (i<first+n-1) System.out.print (", ");
      }
      System.out.println ("]");
   }

   public static void main (String [] args) {
      int [] data  = new int [1000];
      int n = 0;
      for (int i=0; i<args.length; i++) {
	 data[n++] = Integer.parseInt(args[i]);
      }
      printArray (data, n);
      quick_sort (data, n);
      printArray (data, n);
   }

}