Quick sort Implementation

 Quick sort : In quick sort, we will consider a pivot element and divide the array so that all the lesser element will be in left side of pivot element while all the greater element will be in right side.

   This process we will continue recursively until array is fully sorted.
     Time complexity will beO(nlogn) but in worst case when elements are in sorted order time complexity will become O(n^2) as in each call only one element will be consider as sorted and for rest again we need to follow same process.
     space complexity will be O(1).

class QuickSort {

    public static void sort(int[] array) {
        int n = array.length;
        shuffle(array);
        sort(array, 0, n - 1);
    }

    private static void sort(int[] array, int lo, int hi) {
        if (hi <= lo) return;
        int j = partition(array, lo, hi);
        sort(array, lo, j - 1);
        sort(array, j + 1, hi);
    }

    private static int partition(int[] array, int lo, int hi) {
        int i = lo + 1;
        int j = hi;
        int pivot = array[lo];
        while (i <= j) {
            while (array[i] <= pivot) {
                i++;
                if (i > hi) break;
            }
            while (array[j] >= pivot) {
                j--;
                if (j == lo) break;
            }
            if (i >= j) break;
            swap(array, i, j);
        }
        swap(array, lo, j);
        return j;
    }

    private static void shuffle(int[] array) {
        Random random = new Random();
        for (int i = 1; i < array.length; i++) {
            int j = random.nextInt(i + 1); // [0, i]
            swap(array, i, j);
        }
    }

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

    private static void print(int[] array) {
        System.out.print("[");
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i]);
            if (i < array.length - 1) {
                System.out.print(", ");
            }
        }
        System.out.println("]");
    }

    public static void main(String[] args) {
        int[] A = {111, 80, 14, 21, 19, 31, 19, 121, 10, 190, 80, 6, 7};
        sort(A);
        print(A);
    }
}

Please have a look to the  source code of all sorting method from below link

1. BUBBLE SORT PROGRAM
2. SELECTION SORT PROGRAM
3. INSERTION SORT PROGRAM
4. MERGE SORT PROGRAM
5. QUICK SORT PROGRAM