What is the Quicksort Algorithm?
The Quicksort algorithm is a systematic routine for sorting elements of an array. It is efficient when compared to other common sorting algorithms, and it is considered unstable because the relative order of equal elements is not guaranteed. The name "Quicksort" refers to the fact that this algorithm is capable of sorting data much faster than any other traditionally used sorting algorithm.
How does the Quicksort Algorithm work?
The algorithm works by partitioning the array into two smaller sub-arrays with smaller values on one side and larger on the other. This partitioning can then be recursively applied to the sub-arrays to form even smaller partitioned sub-arrays. The base case for the recursion is a sub-array of size one or size zero, which are already sorted by definition. Like the sorting algorithm Merge sort, Quicksort takes the divide and conquer approach to processing data.
Simply put, the Quicksort algorithm takes a data set and splits it in half at a point known as the "pivot." Each half is then sorted the same way, by each being cut in half. The process is then repeated enough times until the small groups can be sorted easily. In the end, the small groups can be easily ordered to produce a fully sorted data set.
When choosing a sorting algorithm, efficiency is often one of the most important factors. Below are some of the efficiency characteristics of the Quicksort algorithm:
Algorithmic Time Complexity - In the best, average, and worst cases, the Quicksort algorithm performs with O(n), O(n log n), and O(n^2) complexities, respectively. It is one of the most efficient sorting algorithms when it comes to time complexity.
Algorithmic Space Complexity - It’s average space complexity is O(log n) and worst case space complexity is O(n). This is on par with most of the popular sorting algorithms, but the nature of recursive algorithms is that they do not optimize around memory usage.
Optimizations - With any algorithm, there are often some optimizations that can be applied above and beyond the general use cases. To make sure that the used space is limited to O(log n), the algorithm can be implemented to recurse into the smaller side of the partition and also use tail recursion. One may also implement a hybrid sorting algorithm that switches to an iterative sorting algorithm that may be more time-efficient for smaller arrays.