Quick2.java

public class Quick2 {

   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>1) {
	 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
      }
   }

   /*
     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 + n/2;
      swap (data, middle, first);
      final int pivot = data[first];

      int tooBigIndex=first+1, tooSmallIndex=first+n-1;
      while (tooBigIndex <= tooSmallIndex) {

	 while (tooBigIndex < first+n && data[tooBigIndex]<=pivot) tooBigIndex++;
	 while (data[tooSmallIndex] > pivot) tooSmallIndex--;

	 if (tooBigIndex<tooSmallIndex) {
	    swap (data, tooBigIndex, tooSmallIndex);
	 }
      }

      // Move the pivot element to its correct position at data[tooSmallIndex]
      data[first] = data[tooSmallIndex];
      data[tooSmallIndex] = pivot;

      return tooSmallIndex;  // 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++) {
         try {
	    data[n++] = Integer.parseInt(args[i]);
         } catch (NumberFormatException e) {
         }
      }
      printArray (data, n);
      quick_sort (data, n);
      printArray (data, n);
   }

}