The Beautiful Quick Sort
Quicksort is a divide and conquers algorithm i.e it divides your given array into two parts and then sorts those two parts separately, it is in some way similar to merge sort but in merge sort, the merge process is complex whereas in quick sort the partition is complex. but that is the reason why we are here, to make the complex process seem not so complex.
Space and Time complexity:
The space complexity is calculated based on the space used in the recursion stack. The worst-case space used will be O(n). The average case space used will be of the order O(long). The worst case space complexity becomes O(n) when the algorithm encounters its worst case where for getting a sorted list, we need to make recursive calls.
How?
Partition is the key function in quicksort and it can be done in the following way:
1. Hoare's partition(preferred):
Like Lomuto partition this also requires O(n) time complexity and O(1) extra space and requires only one traversal of the input array. it is not always that the pivot will be at its correct position. in general, this portion takes fewer comparisons as compared to Lomuto's partition.
Code for quicksort using Hoare's partition :
Why quick sort?
Despite having 0(n²) time complexity, it is faster than merge sort because of the following reasons-
- Inplace algorithm:
“In-place means that the algorithm does not use extra space for manipulating the input but may require a small though nonconstant extra space for its operation. Usually, this space is O(log n), though sometimes anything in O(n) (Smaller than linear) is allowed [Source: Wikipedia].”
Even though calling quicksort an in-place algorithm is arguable but in broad terms, Quicksort does not use extra space for partition or to manipulate the inputs, but only uses extra space for the recursion call functions.
Cache friendly:
Since quicksort in place so it is cache-friendly as well since it is working on the same array or list.
Tail recursive:
As the recursive call is the last thing executed by the list.
Application of quicksort:
1. Commercial computing: Used in various government and private organizations to sort various data like sorting of accounts/profiles by name or any given ID, sorting transactions by time or locations, sorting files by name or date of creation, etc.
2. Numerical computations: Most of the efficiently developed algorithms use priority queues and inturn sorting to achieve accuracy in all the calculations.
3. Information search: Sorting algorithms aid in the better search of information and what faster way exists than to achieve sorting using quicksort.
Interview question:
Is Quick Sort a stable algorithm?
Quicksort is not a stable algorithm because the swapping of elements is done according to the pivot’s position (without considering their original positions). A sorting algorithm is said to be stable if it maintains the relative order of records in the case of equality of keys.
Why Quick Sort is better than Merge Sort?
- Auxiliary Space: Quicksort is an in-place sorting algorithm whereas Merge sort uses extra space. In-place sorting means no additional storage space is used to perform sorting (except recursion stack). Merge sort requires a new temporary array to merge the sorted arrays thereby making Quicksort the better option.
- Worst Cases: The worst-case runtime of quicksort is O(n²) can be avoided by using randomized quicksort as explained in the previous point. Obtaining average-case behavior by choosing random pivot elements improves the performance and becomes as efficient as merge sort.
- Cache Friendly: Quick Sort is also a cache-friendly sorting algorithm as it has a good locality of reference when used for arrays.
