QuickSort

QuickSort.java

import java.util.Arrays;

class QuickSort {

    public static void main(String[] args) {
        QuickSort quickSort = new QuickSort();
        int[] input = new int[]{
                26690, 701, 126, 248845, 17,
                54016, 71347, 99457, 134932,
                1754, 2241, 2957, 3732, 4,
                5449, 6637, 8422, 11453, 15
        };
        System.out.println("INPUT: " + Arrays.toString(input));
        quickSort.sort(input, 0, input.length - 1);
        System.out.println("OUTPUT: " + Arrays.toString(input));
    }

    /**
     * @return the ending index of value lesser than pivot
     * i.e, partition-id. the place where pivot is swapped with.
     */
    private int partition(int[] input, int low, int high) {
        int pivot = input[high];
        int i = low - 1;
        for (int j = low; j < high; j++) {
            if (input[j] < pivot) {
                i++;
                swap(input, i, j);
            }
        }
        swap(input, high, i + 1);
        return i + 1;
    }

    private void sort(int[] input, int low, int high) {
        if (low >= high) {
            return;
        }
        int pid = partition(input, low, high);
        sort(input, low, pid - 1);
        sort(input, pid + 1, high);
    }


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