Quick Sort

Quick sort is making use of recursion so if you are not familiar with recursion, I recommend going through my Introduction to recursion post.

This algorithm also makes use of a technique which is called Divide and Conquer. The basic idea behind it is, instead of dealing with an instance of a problem at its current size, let’s divide it and deal with the smallest possible instances of the given problem.

You may ask, why would you do it in such a way? Well, let’s say you don’t know mathematics at all.You wouldn’t start learning it with “Kinematics of rotating targets”, right? Rather your first steps would be to start with counting numbers 1 through 10. That’s because it is easier that way. The same principle applies here, once we divide a problem into smaller units, the problem is not that scary any more.

How the quick sort works? On the highest level, we classify data as we keep dividing problem into smaller units with each recursive call. So when we reach the smallest possible unit, we notice that problem has resolved almost itself. Let’s look at the pseudo code:

function quick_sort(array_to_sort)
    if length of array_to_sort is max 1
        return array_to_sort
    else
        pivot = find_a_pivot()
        smaller_items = find_values_smallest_then_pivot()
        greater_items = find_values_greater_then_pivot()
        return quick_sort(small_items) + pivot + quick_sort(greater_items)

So our base case (if you not familiar what base case is, please visit my “Introduction to recursion” post) is “if array_to_sort small enough”. This condition makes sure that we won’t end up in an endless loop.

The recursive case contains a pivot and two arrays of items, one smaller than pivot and second greater than pivot. The pivot is an arbitrary index chosen by the implementer (you) and it can be literally anything within the array’s range. But bear in mind that the pivot’s position influences the performance of the algorithm. So if you care about performance you should go for the pivot, which is every time located in the middle of each array. This will result in O(n log n) complexity as an average case, in comparison to O(n²) as a worst case, if your pivot would lay on either far end of each array. Going further, smaller_items are all items that are smaller than the pivot and greater_items are all items that are greater than the pivot. In the end of our recursive case, we merge our results, and when the stack is fully unwound we end up with a sorted array.

Possible implementation in python:

def quick_sort(array_to_sort):
    if len(array_to_sort) <= 1:
        return array_to_sort

    pivot = array_to_sort[len(array_to_sort) // 2]
    smaller = [i for i in array_to_sort if i < pivot]
    greater = [i for i in array_to_sort if i > pivot]

    return quick_sort(smaller) + [pivot] + quick_sort(greater)