Quick Sort

Steps:

1. We select a pivot element and arrange the rest of the array such that all the elements to the left of pivot element should be less than it and to the right of pivot element should be great than it.
2. Now wrt the pivot element, divide the array into two sub arrays: One containing the elements to the left of it and another containing the elements to right of it.
3. Follow the 1st again for these two sub arrays.

Arranging the elements wrt pivot:

1. Select the last element as pivot and pivotIndex as start index.
2. Now starting from the first index of the array, compare each element with pivot. If the element < pivot, then swap the element with the element at pivotIndex element and increase the pivotIndex by 1
3. 2nd step has to be repeated till the last before element

Randomized Quick Sort:
In the above procedure we are always selecting the last element as the pivot. Instead of it, we can select the pivot element randomly in the array. Then swap that element with last element of the array.
Remaining steps are same as above.

Code:

import java.util.Arrays;
import java.util.Random;

class QuickSort {
        static public void quickSort(int[] in, int start, int end) {
                if(start < end) {
                        //int partitionIndex = partition(in, start, end);
                        int partitionIndex = randomizedPartition(in, start, end);

                        quickSort(in, start, partitionIndex-1);
                        quickSort(in, partitionIndex+1, end);
                }
        }

        static int partition(int[] in, int start, int end) {
                int pivot = in[end];
                int pIndex = start;

                for(int i=start; i<end-1; i++) {
                        if(in[i] < pivot) {
                                //exchange pIndex and i index elements
                                int temp = in[i];
                                in[i] = in[pIndex];
                                in[pIndex] = temp;

                                ++pIndex;
                        }
                }

                in[end] = in[pIndex];
                in[pIndex] = pivot;

                return pIndex;
        }

        static int randomizedPartition(int[] in, int start, int end) {

                Random random = new Random();

                int pivotIndex = start + random.nextInt(end-start);

                //swap end and pivotIndex elements

                int tmp = in[pivotIndex];

                in[pivotIndex] = in[end];

                in[end] = tmp;

                int pivot = in[end];

                int pIndex = start;

                for(int i=start; i<end-1; i++) {

                        if(in[i] < pivot) {

                                //exchange pIndex and i index elements

                                int temp = in[i];

                                in[i] = in[pIndex];

                                in[pIndex] = temp;

                                ++pIndex;

                        }

                }

                in[end] = in[pIndex];

                in[pIndex] = pivot;

                return pIndex;

        }

        static public void main(String[] args) {

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

                System.out.println(Arrays.toString(in));

                quickSort(in, 0, in.length-1);

                System.out.println(Arrays.toString(in));

        }

}

eg:
{8, 5, 1, 4, 2, 7, 6, 3}

1st Iteration:
pivot = 3
Compare 8 with 3. Since 8 > 3, dont do anything
Compare 5 with 3. Since 5 > 3, dont do anything
Compare 1 with 3. Since 1 < 3, exchange pivotIndex(0) element with current element.
==> {1, 5, 8, 4, 2, 7, 6, 3}
Increase pivotIndex by 1 ==> pivotIndex = 1

Compare 4 with 3. Since 4 > 3, dont do anything
Compare 2 with 3. Since 2 < 3, exchange pivotIndex(1) element with current element.
==> {1, 2, 8, 4, 5, 7, 6, 3}
Increase pivotIndex by 1 ==> pivotIndex = 2

Compare 7 with 3. Since 7 > 3, dont do anything.
Compare 6 with 3. Since 6 > 3, dont do anything.

Since pivotIndex is 2, exchange the last element with element at index 2
==> {1, 2, 3, 4, 5, 7, 6, 8}

Here you can see that the pivot element is now at correct position, as like in sorted array.

Now divide the array wrt pivot element: ==> {1, 2} and {4, 5, 7, 6, 8}.
Follow the above procedure for these two arrays well.

Complexity: