Like Merge Sort, Quicksort is a divide and conquer algorithm. Quicksort first divides the array into two smaller sub-arrays around a picked element called Pivot. Then recursively sort the sub-arrays. It works as follows:
- Pick an element, called a pivot, from the array.
- Reorder the array such that all the elements before pivot are less than pivot value, while all elements after pivot are grater than or equal to pivot. After this operation, the pivot is in its final position. This is the key process in quicksort, called the partition().
- Recursively apply this to the sub-arrays before and after the pivot. Look at this example.
There are different variants of Quicksort that pick pivots in different ways:
- First element of array.
- Last element of array.(used in the following implementation)
- Random element of array.
- Middle index element of array.
Time complexity : O( N log N -- N log N -- N² ) [Best -- Average -- Worst] Memory : O(N or log N) # auxiliary i.e. apart from storing input array Stable : No i.e. can change relative order of elements with same key # N being the number of elements in the array
Other popular sorting algorithms’ complexities are given here.
Usage and advantages
Although the worst case time complexity of QuickSort is O(n2) which is more than many other sorting algorithms like Merge Sort and Heap Sort, QuickSort is faster in practice, because its inner loop can be efficiently implemented on most architectures, and in most real-world data. Quicksort gained widespread adoption, appearing, for example, in Unix as the default library sort function, hence it lent its name to the C standard library function qsort and in the reference implementation of Java.
Bottom Line: Quicksort is often faster in practice than other O(n log n) algorithms.
Implementation in C:
Question: Sort an array of integers in increasing order using quicksort algorithm (format similar to most of the online programming contests )
First line of the input contains T, number of test cases
Each test case contains an integer N ≤ 200, the number of integers in that array, followed by N integers separated by N spaces.
Output: Sorted array
3 5 4 7 9 3 1 3 4 5 5 4 6 10 6 7
1 3 4 7 9 4 5 5 6 6 7 10
Brief explanation is given in the gist.