Algorithms: QuickSort

Quicksort as name suggests is the one of the quick technique to sort array of elements.

Now Question is, is it the best one ? No, not at all, we have many other sorting algorithms better than it.

Still you should have a very good understanding of Quicksort.

Quicksort works on the Divide and Conquer strategy. 

It divides the whole array around an element of the array (we will call it Pivot), and try to arrange the elements in such a way that elements to the left of the array are smaller than it (might not be sorted) and elements to the right of Pivot are all greater than it    (might not be sorted).

Once you finish this activity, you are sure that the Pivot element is at the right position in the array.

Do the same to the left and right subarrays around the Pivot element recursively and you are done.

Just before moving to the code:
1. I have explained every step as comments in the code, so please read process in code only.

2. We can select any element as Pivot, it could be 1st element, last element or middle or any random. generally I choose middle, however it is not the most efficient.

3. When we write any recursive method we always have to think before hand when to break the recursion, so have this in mind.

4. Best case time complexity is O(nlogn)

5. Worst case time complexity is O(n*n) in case of worst choice of pivot or already sorted.

6. in Java 8, Quicksort is used for primitive elements array, however Mergesort is used for Objects array.

Github link

lets write some code:

package madwani.sushil.sorting;

import madwani.sushil.Util;

public class QuickSort {

    public static void main(String[] args) {

        String input = Util.readLine();

        int[] elements = Util.convertLineToIntArray(input);

        quicksort(elements, 0, elements.length-1);

        Util.print1dArray(elements);

    }

    public static void quicksort(int[] arr, int start, int end) {

        // basic check to ensure corner case

        if (arr == null || arr.length == 0) {

            return;

        }

        // condition to break recursion

        if (start >= end) {

            return;

        }

        // I always chose middle element as Pivot

        int middle = start + (end - start) / 2;

        // Pivot element

        int pivot = arr[middle];

        // lets start the real sorting

        int i = start, j = end;

        // do comparison and swapping till start and end have not met

        while (i <= j) {

            // increment till left side elements are lesser or equal to pivot

            while (arr[i] <= pivot) {

                i++;

            }

            // decrement till right side elements are greater to pivot

            while (arr[j] > pivot) {

                j--;

            }

            // swap elements from left right only when indices haven't crossed each other

            // after swap always increase lower index and decrease higher index

            if (i <= j) {

                Util.swapElementsInArray(arr, i, j);

                i++;

                j--;

            }

        }

        // one pass is done, so we have 2 boundaries
        // lower boundary: i which was moving towards end
        // upper boundary: j which was moving towards start



        // if i has not reached and crossed the end lets do one more pass from i to end
        // this is left subarray

        if (end > i) {
            quicksort(arr, i, end);
        }

        // if j has not reached the start and crossed, lets do one more pass from start to j
        // this is right subarray

        if (start < j) {
            quicksort(arr, start, j);
        }
    }
}