Sms
Email
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.
QuickSort
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.
To summarize, the steps of this part of the algorithm are:
- Set the initial pivot point as the median of the first, middle, and last elements. We'll discuss this in more detail below.
- Iterate through the array and compare values against p.
- 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.
- Consider the left partition to be the subarray from the beginning to p and the right partition to be the subarray from p+1 to the end.
There are multiple ways we can approach creating the partition function. In our implementation, we will use two pointers, one for the left and one for the right. The left will start at the leftmost part of the array and the right will start at the rightmost. Both sides will increment/decrement until a mismatch pair is found, then swap them. The full steps are:
- Initialize left to the beginning and right to the end indices.
- Move the left pointer forwards until an item equal to or larger than p is found.
- Move the right pointer leftwards until an item equal to or lesser than p is found.
- If right is less than or equal to left, the partition process is complete, and right is the partition index.
- Otherwise, swap the array values at left with right, then move back to step 2.
Pivot Selection
There are multiple ways a pivot can be selected. The selected pivot can have consequences on the overall performance. Common types of pivot choices include:
- First index: we can make the pivot point the first possible index. However, this is generally avoided, as it can cause the algorithm to degrade to O(n^2) for lists which are sorted or mostly sorted. This point will be covered further in sections below.
- Mid-point index: we can make the pivot point the middle index in the array.
- Last index: we can make the pivot point the last possible index.
- Random index: select any random index as the pivot.
- Median of three: take the first, center, and last elements, determine the median value of the three, and use that value. This is the approach we will be taking in our algorithm.
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.
Recursively Sorting
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.
Complexity Analysis
In the table below, we'll outline the space complexity, time complexity, and other aspects of the quicksort algorithm:
| Value | Notes | |
|---|---|---|
| Space Complexity | O(n) | This requres space in the function call stack for recursive calls. Average case is O(log n) |
| Time Complexity | O(n^2) | The average case is O(n logn), but in edge cases, such as an array which is already sorted, performance will degrade to O(n^2) |
| 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.
Full Implementation
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.