|In Brief||Quicksort is a fast, recursive, divide and conquer algorithm developed by Charles Antony Richard Hoare. It is believed to be the fastest sorting algorithm, in practice [Weiss1999].... more|
1 function quicksort(array)
3 if len(array) <= 1
4 return array
6 pivot = pick_pivot(array) // Function to pick a pivot
8 array_1 =  // Empty sequence
9 array_2 =  // Empty sequence
11 foreach x in array
12 if x <= pivot
17 return quicksort(array_1) + pivot + quicksort(array_2) // Append the arrays
Quicksort is a fast, recursive, divide and conquer algorithm developed by Charles Antony Richard Hoare. It is believed to be the fastest sorting algorithm, in practice [Weiss1999].
This algorithm operates by choosing a pivot, then splitting the unsorted array into two sub-arrays along the pivot, where one of the sub-arrays contains the elements with a value less than the pivot and the other array contains the elements with a value greater than the pivot. After the sub arrays are sorted, they are joined and the resulting sequence is sorted. Although if the arrays are sorted in place, no joining is necessary.
There are two key differences between QuickSort and Merge Sort, in QuickSort the arrays are split along a pivot, not along the middle, and since the array can be sorted in-place, only enough memory for the unsorted sequence is needed.
For a rigorous mathematical definition and analysis of QuickSort, and for a good algorithm on performing the partition in place see [Cormen2001].
Choosing a Pivot
The easiest way to pick a pivot that will results in good performance is to select it at random. Never pick the first or last elements as a pivot because if the array is already sorted in forward or reverse order, the algorithm will operate with extremely poor performance.
Without knowing more about the distribution of the sequence values, one of the best ways to pick a pivot is to choose the median of three numbers in the array, [Weiss1999] recommends the median of the first, last and middle element of the array, as this should result in good performance for arrays already in sorted order.
A key optimization of Quicksort is to partition the array in place, this not only reduces the memory footprint and overhead caused by memory allocations but also removes the need to join the sorted sub-arrays.
Another optimization stems from the fact that Quicksort is not very efficient for small arrays ( < 10-20 elements). Thus it is common, and advised, to switch to a more efficient algorithm at a cutoff of around 10 or 20 elements, [Weiss1999] claims that this approach can result in a 15% performance boost. For an algorithm suitable for this purpose is Insertion Sort.
|[Weiss1999]||(1, 2) Mark Allen Weiss. Data Structures & Algorithm Analysis in C++|
|[Cormen2001]||Thomas H. Cormen, et al. Introduction To Algorithms, 2001|
Quicksort is one of the most popular sorting algorithm, as such a query on your favorite search engine for Quicksort, will provide you with lots of information on the algorithm, it's performance and implemenation.
Another good starting point for QuickSort variants and implementations is the Wikpedia entry on QuickSort.