Quicksort is one of the most efficient and most fundamental sorting algorithms. The algorithm is based on a recursive divide and conquer approach. It is also one of the classic algorithms taught and tested in universities. In this article, we'll introduce quicksort, discuss how it works, its space and time complexity, and give full code examples in multiple languages. Before proceeding, if you are not familiar with recursion, please visit our non-techincal introduction to recursion or our outline on writing recursive functions.
The quicksort algorithm is a comparison based sorting algorithm which is used to sort a list of items. Generally, it is applied to sort arrays. This algorithm uses a divide and conquer approach to recursively sort different partitions of the main array, continuously making smaller and smaller partitions, and partially sorting each partition based on a pivot value, until each partition is of size one. Once this point is reached, the sort process will be complete and the entire array will be sorted in place. The original array itself will be sorted, thus the original ordering will be lost. We'll break down the process step by step and give a full overview of each step in the following sections.
Pivoting and Partitioning
Quicksort applies the divide and conquer strategy by dividing the input array into partitions. At each recursive step, a partition will be created by selecting a pivot point within the array, then swapping items in the array so all items smaller than the pivot are to the left, and all items larger are to the right. This isn't a full sort, as items to the left and right might still be unsorted themselves. We can consider the array to be sorted with respect to "p", where p is the pivot value. Once the pivot process is complete, we will have two partitions, one with values smaller than or equal to p and one with values larger than or equal to p. The value p itself is now in the position it will be in once the entire array is sorted.
- If the item is before p but greater than p, move it to the right of p.
- If the item is after p but less than p, move it to the left of p.
The ideal pivot value is a value which is the median of all of the values in the array. The median of three pivot approach will increase the chances of using a median value as the pivot point by selecting the best option out of three items. In the worst case scenario, all values will be the same. In the best case, all values will be different and the median selected will be closer to the median of the entire array than the other two values.
Once the partitioning process is complete, the array will be sorted in respect to the pivot. Additionally, we will have two partitions, a left partition and right partition. Note that the pivot index itself is excluded from both partitions. To continue the sorting process, we can recursively call the quicksort algorithm once for each partition. This will recursively sort each partition as if it were its own array; they will have their own pivot points, operations, etc. Instead of cloning or splicing arrays, we will pass start and end indices to recursive calls in our implementatino.
In the table below, we'll outline the space complexity, time complexity, and other aspects of the quicksort algorithm:
|Space Complexity||O(n)|| This requres space in the function call stack for recursive calls. Average case is |
|Time Complexity||O(n^2)|| The average case is |
|In Place||Yes||This only requires space on the call stack, unlike a sorting algorithm such as merge sort, which must duplicate subarrays.|
|Stable||No||The sorted array is not guaranteed to preserve the order of items which have an equal sort value.|
|Modifies the Source Input||Yes||The source array itself will be directly modified, so the original ordering will be lost.|
Quicksort is generally considered an O(n logn) sorting algorithm despite its worst case of O(n^2) because an actual performance of O(n^2) is very uncommon, and the average performance is generally faster than other O(n logn) sorting algorithms.
In this implementation, we will be sorting arrays of numbers. However, the approach can be adapted to other types, such as strings and class instances, or generalized to sort anything which can implement a compare method.