The Java Program: QuickSort.java

  1 import Sorter;
  2 
  3 public class QuickSort implements Sorter {
  4 
  5    public void sort (int [] a) { sort (a, 0, a.length-1); }
  6 
  7    private int find_pivot (int [] a, int i, int j) { return (i+j)/2; }
  8 
  9    private void swap (int [] a, int i, int j) {
 10       int T = a[j];
 11       a[j] = a[i];
 12       a[i] = T;
 13    }
 14         
 15    private int partition (int [] a, int l, int r, int p) {
 16       do {
 17          while (a[++l]<p);
 18          while ((r>0) && a[--r]>p);
 19          swap (a, l, r);
 20       } while (l < r);
 21       swap (a, l, r);
 22       return l;
 23    }
 24    
 25    private void sort (int [] a, int i, int j) {
 26       int p = find_pivot (a, i, j);
 27       swap (a, p, j);   // pivot at end
 28       int k = partition (a, i-1, j, a[j]);
 29       swap (a, k, j);   // put pivot in place
 30       if (k-i > 1) sort (a, i, k-1);
 31       if (j-k > 1) sort (a, k+1, j);
 32    }
 33 
 34 }