/*
  Based on the program presented at:
  http://www.java2novice.com/java-sorting-algorithms/quick-sort/
*/

package com.java2novice.sorting;
 
public class MyQuickSort {
     
    private int array[]; // the array to sort
    private int length; // the length of the array
 
    public void sort(int[] inputArr) {
         
        if (inputArr == null || inputArr.length == 0)
            return;

        this.array = inputArr;
        length = inputArr.length; /* don't hardcode the length
        length = 27;
        call the sorting routine */ quickSort(0, length - 1);
    }
 
    private void quickSort(int lowerIndex, int higherIndex) {
        int i = lowerIndex;
        int j = higherIndex;
        // calculate pivot number (the number in the middle of the array)
        int pivot = array[lowerIndex+(higherIndex-lowerIndex)/2];
        // divide into two arrays
        while (i <= j) {
            /**
             * In each iteration, we will identify a number from the left side
             * which is greater than the pivot value, and also we will identify
             * a number from the right side which is less than the pivot value.
             * Once the search is finished, we exchange both numbers.
             */
            while (array[i] < pivot) {
                i++;
            }
            while (array[j] > pivot) {
                j--;
            }
            if (i <= j) {
                exchangeNumbers(i, j);
                // move index to next position on both sides
                i++;
                j--;
            }
        }
        // call quickSort() method recursively
        if (lowerIndex < j)
            quickSort(lowerIndex, j);
        if (i < higherIndex)
            quickSort(i, higherIndex);
    }
 
    private void exchangeNumbers(int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
     
    public static void main(String a[]) {
         
        MyQuickSort sorter = new MyQuickSort();
        int[] input = {24,2,45,20,56,75,2,56,99,53,12};
        sorter.sort(input);
        for(int i:input) {
            System.out.print(i);
            System.out.print(" ");
        }
    }
}