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.