QuickSort, also known as partition-exchange sort, is a highly efficient, comparison-based sorting algorithm. Originally developed by Tony Hoare in 1960 during his work on machine language translation, it operates on a divide et impera strategy.
It selects a pivot element from the array and partitions the remaining elements into two groups: those less than the pivot and those greater than the pivot. This process is recursively applied to the two partitions, breaking down a large sorting problem into smaller, more manageable ones until the entire array is sorted.
Over the years, QuickSort has firmly established its status as a commonly used sorting algorithm in the software industry.
How it works
It operates on the following key points:
- Pivot selection: Initially, the algorithm chooses a pivot element from the array. The pivot can be chosen randomly or through a specific strategy, often it's the first, middle, or last element.
- Partitioning: Post pivot selection, the array is rearranged such that all elements smaller than the pivot are moved before it and all elements larger are moved after it. This process is referred to as partitioning. Upon the completion of this step, the pivot element is in its final position in the sorted array.
- Recursion: The algorithm then recursively applies the same operations to the two partitions, i.e., the elements less than the pivot and those greater than the pivot. This process continues, recursively dividing the array until only one element remains in each partition. At this stage, since each single-element array is inherently sorted, the entire array becomes sorted.
Here is a simple implementation in C#:
public void QuickSort(int[] arr, int left, int right)
{
if (left < right)
{
var pivot = Partition(arr, left, right);
QuickSort(arr, left, pivot - 1);
QuickSort(arr, pivot + 1, right);
}
}
public int Partition(int[] arr, int left, int right)
{
var pivot = arr[right];
var i = left - 1;
for (var j = left; j <= right - 1; j++)
{
if (arr[j] < pivot)
{
i++;
Swap(ref arr[i], ref arr[j]);
}
}
Swap(ref arr[i + 1], ref arr[right]);
return i + 1;
}
public void Swap(ref int a, ref int b)
{
(a, b) = (b, a);
}
To use the above implementation, you simply need to call the QuickSort
method with your array and the lowest and highest indexes as arguments. For instance, if an array of integers is known as arr
, the sorting process would be initiated by executing the corresponding method call:
QuickSort(arr, 0, arr.Length - 1);
Time complexity
The time complexity in the best and average case is O(n log n) making it a compulsory choice for large data sets. In the worst-case scenario, that is, when the input array is already sorted, its time complexity becomes O(n²).
Space complexity
The space complexity is O(log n). This mirrors the space required to accommodate the stack of recursive calls. However, it is worth mentioning that this can vary depending on the intricacies of the implementation and the pivot selection strategy. Generally, it performs impressively in terms of space complexity, making it a good choice when memory is a consideration.
Conclusion
QuickSort is a highly effective and adaptable sorting algorithm that is extensively used when dealing with large datasets. Its performance may taper in certain edge cases, but overall, it delivers an excellent balance of time and space efficiency, making it a preferred choice across a range of data management scenarios.
References
- Algoritmi e programmazione in C di Francesco Oliveri, Aracne editrice (Italian book)
Top comments (2)
Thanks for the walkthrough.
Which algorithm is a better choice out of Quick Sort and Merge Sort? If I understand correctly, they're both O(n log n) complexity.
The choice between MergeSort and QuickSort depends on several factors, including the type of input data, system resources, and the specific application.
QuickSort has a time complexity of O(n log n) in the average case, equal to that of MergeSort. However, in the worst case it is O(n²), which is significantly less efficient. One advantage of QuickSort is that it is an in-place sorting algorithm, meaning it does not require additional memory space, aside from a small function stack. Yet, the efficiency of QuickSort can greatly depend on the pivot's choice.
MergeSort on the other hand has a time complexity of O(n log n) in both the average and worst case, making it more efficient than QuickSort. But, unlike QuickSort, MergeSort requires additional memory space proportional to the input size, as it is not an in-place algorithm. An additional advantage of MergeSort is that it is stable, that is, it maintains the relative order of equal elements, while QuickSort is not.
In conclusion, if the relative order of equal elements is important and memory space is not a concern, then MergeSort might be the better choice. Conversely, if memory space is a key consideration, then QuickSort might be the preferable choice. Also, sometimes, an efficient implementation of QuickSort can outperform MergeSort for some types of data.