Quick Sort

Intro

Quick sort is an efficient sorting algorithm, that is based on the divide and conquer approach.
Just like with the Merge sort, it divides the array into smaller sub-arrays and applies the solution to the smaller parts first.
It has a time complexity of O(n log n) - the same as Merge sort.

Quick sort - how does it work?

In Quick Sort, we follow three steps:

1. Pivot Selection - We pick an element and mark it as a pivot. The pivot element can be the first element, last element, or any random element
2. Partitioning - We reorder the array such that all elements greater than the pivot come after the pivot and all elements smaller than the pivot come before the pivot. The elements equal to the pivot can go either side of the pivot. After this partitioning, the pivot is at its correct sorted position.
3. Recursion - Recursively apply the above steps on the subarray formed on the left side of the pivot and on the subarray formed on the right side of the pivot.

So we first pick the pivot, then we reorder the elements so that every element that is smaller than the pivot goes left and every element that is greater than the pivot goes right and we finish by placing the pivot at its correct position inside the array and we never touch it again.

After that, we recursively call the sort method on both sides of the pivot, but excluding the pivot itself, because we know that it is in its correct position already.

Here is one good illustration of how this algorithm works:

 

As you can see, we apply the same logic to the left and right sides of the pivot, after we place it to its correct position. And we end up getting all elements at their correct position inside the array.

Let's code it

Below is the Java implementation of the Quick sort algorithm

public class QuickSort {

    public void quickSort(int[] arr, int begin, int end) {
        if (begin < end) { // BASE CASE
            int partitionIndex = partition(arr, begin, end);

            quickSort(arr, begin, partitionIndex - 1);
            quickSort(arr, partitionIndex + 1, end);
        }
    }

    private int partition(int[] arr, int begin, int end) {
        int pivot = arr[end];
        int i = (begin - 1);

        for (int j = begin; j < end; j++) {
            if (arr[j] <= pivot) {
                i++;

                int swapTemp = arr[i];
                arr[i] = arr[j];
                arr[j] = swapTemp;
            }
        }

        int swapTemp = arr[i + 1];
        arr[i + 1] = arr[end];
        arr[end] = swapTemp;

        return i + 1;
    }
}

Inside the partition method, we use two pointers - i and j. We set i to start - 1, and j to start.
While we iterate through array when we find an element that is greater than the pivot, we increment j, and when we find an element that is less or equal to the pivot, we increment i and swap elements on i and j positions. 

So we know when we increment i, it will be pointing to the number that is greater than the pivot. Because when we move the j pointer, we leave behind elements that are greater than the pivot, so that i can point to them when we need to swap with smaller elements.

Quick sort - analysis

Quick sort has best case and average case time complexity of O(n log n) and worst case complexity of O(n^2).

Best and average case O(n log n) - The best case scenario for quicksort occurs when the pivot chosen at each step divides the array into roughly equal halves. In this case, the algorithm will make balanced partitions, leading to efficient sorting. On other occasions, the average case is still O(n log n) which makes this algorithm suitable for sorting large sets of data.

Worst case O(n^2) - When elements are sorted, reverse sorted or all elements are the same. This can cause highly unbalanced partitions.

When an array is sorted we take the leftmost element as the pivot element.
After partitioning around the pivot, we will have two sub-arrays one with 0 elements and the other with n-1.

When an array is reverse sorted we take the rightmost element as the pivot element. After partitioning around the pivot, again we will have two sub-arrays one with 0 elements and the other with n-1.

When all elements of the array are the same, we take either left leftmost element or the rightmost element as the pivot element, It splits the array into one sub-array of size n-1 due to which the performance of this algorithm decreases significantly.

In all the above scenarios, we need to iterate the complete sub-arrays every time.

The space complexity of Quick sort is O(1) - because we don't need any extra memory space since we are not creating any new data structures.

Quick sort is an unstable algorithm.