package algorithm.sort;

public class QuickSort {

    public static void main(String[] args) {

       int[] a = new int[] {5, 3, 7, 2, 1, 4, 9, 8, 6, 1};

       sort(a);

       print(a);

    }

    public static void sort(int[] a) {

       sort(a, 0, a.length - 1);

    }

    public static void sort(int[] a, int p, int r) {

       if (p < r) {

           int q = partition(a, p, r);

           sort(a, p, q - 1);

           sort(a, q + 1, r);

       }

    }

    private static int partition(int[] a, int p, int r) {

       int x = a[p];

       int i = p;

       for (int j = p + 1; j <= r; j++) {

           if (a[j] <= x) {

              i++;

              exchange(a, i, j);

           }

       }

       exchange(a, i, p);

       return i;

    }

    public static void exchange(int[] a, int i1, int i2) {

       int tmp = a[i1];

       a[i1] = a[i2];

       a[i2] = tmp;

    }

    public static void print(int[] a) {

       if (a == null || a.length == 0)

           return;

       for (int i = 1; i <= a.length; i++) {

           System.out.print(a[i - 1] + "\t");

           if (i % 5 == 0)

              System.out.println();

       }

    }

}