This lesson's interactive features are locked, please to keep using them
Fixing Quick Sort
While the version of quicksort that we implemented is almost always able to perform at speeds of O(n*log(n)), its Big O is still technically O(n^2) due to the worst-case scenario. We can fix this by altering the algorithm slightly.
Two of the approaches are:
- Shuffle input randomly before sorting. This can trivially be done in
O(n)time. - Actively find the median of a sample of data from the partition, this can be done in
O(1)time.
Random Approach
The random approach is easier to code, which is nice if you're the one writing the code.
The function simply shuffles the list into random order before sorting it, which is an O(n) operation. The likelihood of shuffling a large list into sorted order is so low that it's not worth considering.
Median Approach
Another popular solution is to use the "median of three" approach. Three elements (for example: the first, middle, and last elements) of each partition are chosen and the median is found between them. That item is then used as the pivot.
This approach has less overhead, and also doesn't require randomness to be injected into the function, meaning it can remain deterministic and pure.