Quick Sort

Time complexity average case: O(n log n)
Time complexity worst case: O(n²)

Quicksort is nlogn most of the time & usually 2 or 3 times quicker than MergeSort but can be n² in some cases, e.g when the numbers are already sorted in my implementation below. It is a divide and conquer algorithm. It uses a pivot to partition numbers smaller and bigger than the pivot on each side of the pivot. There are various ways to choose a pivot including the median item and last item. There are also a huge amount different ways in which you can implement the rest of the logic in the quick sort. In the gist below I have implemented a quick sort algorithm similar to Robert Sedgewick’s in his algorithms book.

https://gist.github.com/adamkorg/c180fc4f07331da04953348369b9c28a

In the above I do a pass with two pointers iterating from left end and right end, switching items bigger than the pivot from left with items smaller than pivot from right. Once the two pointers cross, I then switch the value of the pointer that started on the left with the pivot (right most element). Then recursively do the same on partitions left and right of pivot. Below are my Quicksort whiteboard notes showing the steps and passes:

It is quite easy make an iterative version using a stack data structure, which simulates the recursive call stack:

https://gist.github.com/adamkorg/6bd95d1ed5ceab468b6d525909d3c78b

This entry was posted in programming and tagged , . Bookmark the permalink.

Leave a Reply

Your e-mail address will not be published. Required fields are marked *