Quicksort
|
|
Quicksort_example_small.png
Quicksort is a well-known sorting algorithm developed by C. A. R. Hoare that, on average, makes Θ(n log n) comparisons to sort n items. However, in the worst-case, it makes O(n2) comparisons. Typically, quicksort is significantly faster in practice than other Θ(n log n) algorithms, because its inner loop can be efficiently implemented on most architectures, and in most real-world data it is possible to make design choices which minimize the possibility of requiring quadratic time.
| Contents |
The algorithm
Quicksort sorts by employing a divide and conquer strategy to divide a list into two sub-lists.
The steps are:
- Pick an element, called a pivot, from the list.
- Reorder the list so that all elements which are less than the pivot come before the pivot and so that all elements greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
- Recursively sort the sub-list of lesser elements and the sub-list of greater elements.
The base case of the recursion are lists of size zero or one, which are always sorted. The algorithm always terminates because it puts at least one element in its final place on each iteration.
In simple pseudocode, the algorithm might be expressed as:
function quicksort(a)
var list less, pivotList, greater
if length(a) ≤ 1 {
return a
} else {
select a pivot value pivot from a
for each x in a except the pivot element
if x < pivot then add x to less
if x ≥ pivot then add x to greater
add pivot to pivotList
return concatenate(quicksort(less), pivotList, quicksort(greater))
}
Version with in-place partition
The disadvantage of the simple version above is that it requires Ω(n) extra storage space, which is as bad as mergesort. The additional memory allocations required can also drastically impact speed and cache performance in practical implementations. There is a more complicated version which uses an in-place partition algorithm and can achieve O(log n) space use on average for good pivot choices:
function partition(a, left, right, pivotIndex)
pivotValue := a[pivotIndex]
swap(a[pivotIndex], a[right]) // Move pivot to end
storeIndex := left
for i from left to right-1
if a[i] <= pivotValue
swap(a[storeIndex], a[i])
storeIndex := storeIndex + 1
swap(a[right], a[storeIndex]) // Move pivot to its final place
return storeIndex
This is the in-place partition algorithm. It partitions the portion of the array between indexes left and right, inclusively, by moving all elements less than a[pivotIndex] to the beginning of the subarray, leaving all the greater than or equal elements following them. In the process it also finds the final position for the pivot element, which it returns. It temporarily moves the pivot element to the end of the subarray, so that it doesn't get in the way. Because it only uses exchanges, the final list has the same elements as the original list. Notice that an element may be exchanged multiple times before reaching its final place.
Once we have this, writing quicksort itself is easy:
function quicksort(a, left, right)
if right > left
select a pivot value a[pivotIndex]
pivotNewIndex := partition(a, left, right, pivotIndex)
quicksort(a, left, pivotNewIndex-1)
quicksort(a, pivotNewIndex+1, right)
This version is the one more typically used in imperative languages such as C.
Performance details
Quicksort's inner loop, which performs the partition, is amenable to optimization on typical modern machines for two main reasons:
- All comparisons are being done with a single pivot value, which can be stored in a register.
- The list is being traversed sequentially, which produces very good locality of reference and cache behavior for arrays.
This close fit with modern architectures makes quicksort one of the fastest sorting algorithms on average. Because of this excellent average performance and simple implementation, quicksort has become one of the most popular sorting algorithms in practical use.
Although it is often believed to work in-place, quicksort uses O(log n) additional stack space on average in recursive implementations and O(n) stack space in the worst case.
The most crucial concern of a quicksort implementation is the choosing of a good pivot element. A naïve implementation of quicksort, like the ones below, will be terribly inefficient for certain inputs. For example, if the input is already sorted, a common practical case, this implementation of quicksort degenerates into a selection sort with O(n2) running time. Furthermore, the recursion depth becomes linear, requiring O(n) extra stack space.
This worst-case performance is much worse than comparable sorting algorithms such as heapsort or merge sort. However, if pivots are chosen randomly, most poor choices of pivots are unlikely; the worst-case, for example, has only probability 1/n! of occurring. This variation, called randomized quicksort, can be shown to use O(n log n) comparisons on any input with very high probability.
Note that the partition procedure only requires the ability to traverse the list sequentially; therefore, quicksort is not confined to operating on arrays (it can be used, for example, on linked lists). Choosing a good pivot, however, benefits from random access, as we will see.
Choosing a better pivot
The worst-case behavior of quicksort is not merely a theoretical problem. When quicksort is used in web services, for example, it is possible for an attacker to deliberately exploit the worst case performance and choose data which will cause a slow running time or maximize the chance of running out of stack space. See competitive analysis for more discussion of this issue.
Sorted or partially sorted data is quite common in practice and a naïve implementation which selects the first element as the pivot does poorly with such data. To avoid this problem the middle element may be chosen. This works well in practice, but attacks can still cause worst-case performance.
Another common choice is to randomly choose a pivot index, typically using a pseudorandom number generator. If the numbers are truly random, it can be proven that the resulting algorithm, called randomized quicksort, runs in an expected time of Θ(n log n). Unfortunately, although simple pseudorandom number generators usually suffice for choosing good pivots, they are little defense against an attacker who can run the same generator to predict the values.
A better choice is to select the median of the first, middle and last elements as the pivot. Furthermore, adding two randomly selected elements resists chosen data attacks, especially if a cryptographically secure pseudo-random number generator is used to reduce the chance of an attacker predicting the "random" elements. The use of the fixed elements reduces the chance of bad luck causing a poor pivot selection for partially sorted data when not under attack. These steps increase overhead, so it may be worth skipping them once the partitions grow small and the penalty for poor pivot selection drops.
Interestingly, since finding the true median value to use as the pivot can be done in O(n) time (see selection algorithm), the worst-case scenario can be completely removed while maintaining O(n log n) performance. Because the median algorithm is relatively slow in practice, however, this algorithm is rarely useful; if worst-case time is a concern, other sort algorithms are generally preferable.
Partitioning concerns
As virtually all of the quicksort computation time is spent partitioning, a good partitioning implementation is important. In particular, if all of the elements being partitioned are equal, the above partition algorithm degenerates into the worst-case and needlessly swaps identical elements. This becomes a serious problem in any datasets which contain many equal elements, as many of the 'bottom tier' of partitions will become uniform.
A good variation in such cases is to test separately for elements equal to the pivot and store these in a 'fat pivot' in the center of the partition. Here is an adaptation of our original pseudocode implementation for fat pivots:
function quicksort(a)
list less, equal, greater
if length(a) ≤ 1 {
return a
} else {
select a pivot value pivot from a
for each x in a
if x < pivot then add x to less
if x = pivot then add x to equal
if x > pivot then add x to greater
return concatenate(quicksort(less), equal, quicksort(greater))
}
The way that partitioning is done determines whether or not a quicksort implementation is a stable sort. Typically, in-place partitions are unstable, while not-in-place partitions are stable. The example shown in the pseudocode above is unstable because its exchanges can move a value over other values equal to it.
Other optimizations
Using different algorithms for small lists
Another optimization is to switch to a different sorting algorithm once the list becomes small, perhaps ten or less elements. Insertion sort or selection sort might be inefficient for large data sets, but they are often faster than quicksort on small lists, requiring less setup time and less stack manipulation.
One widely used implementation of quicksort, that in the 1997 Microsoft C library, used a cutoff of 8 elements before switching to insertion sort, asserting that testing had shown that to be a good choice. It used the middle element for the partition value, asserting that testing had shown that the median of three algorithm did not, in general, increase performance.
Sedgewick (1978) suggested an enhancement to the use of simple sorts for small numbers of elements, which reduced the number of instructions required by postponing the simple sorts until the quicksort had finished, then running an insertion sort over the whole array. This is effective because insertion sort requires only O(kn) time to sort an array where every element is less than k places from its final position.
LaMarca and Ladner (1997) consider "The Influence of Caches on the Performance of Sorting", a significant issue in microprocessor systems with multi-level caches and high cache miss times. They conclude that while the Sedgewick optimization decreases the number of instructions, it also decreases locality of cache references and worsens performance compared to doing the simple sort when the need for it is first encountered. However, the effect was not dramatic and they suggested that it was starting to become more significant with more than 4 million 64 bit float elements. Greater improvement was shown for other sorting types.
Another variation on this theme which is becoming widely used is introspective sort, often called introsort. This starts with quicksort and switches to heapsort when the recursion depth exceeds a preset value. This overcomes the overhead of increasingly complex pivot selection techniques while ensuring O(n log n) worst-case performance. Musser reported that on a median-of-3 killer sequence of 100,000 elements running time was 1/200th that of median-of-3 quicksort. Musser also considered the effect of Sedgewick's delayed small sorting on caches, reporting that it could double the number of cache misses when used on arrays, but its performance with double-ended queues was significantly better.
Limiting worst-case memory usage
Because recursion requires additional memory, quicksort has been implemented in a non-recursive, iterative form. This in-place variant has the advantage of predictable memory use regardless of input, and the disadvantage of considerably greater code complexity. A simpler in-place sort of competitive speed is heapsort.
A simple alternative for reducing quicksort's memory consumption is to use true recursion only on the smaller of the two sublists and tail recursion on the larger. This limits the additional storage of quicksort to Θ(log n); even for huge lists, this variant typically requires no more than roughly 100 words of memory. The procedure quicksort in the pseudocode with the in-place partition would be rewritten as
function quicksort(a, left, right)
while right > left
select a pivot value a[pivotIndex]
pivotNewIndex := partition(a, left, right, pivotIndex)
if (pivotNewIndex-1) - left < right - (pivotNewIndex+1)
quicksort(a, left, pivotNewIndex-1)
left := pivotNewIndex+1
else
quicksort(a, pivotNewIndex+1, right)
right := pivotNewIndex-1
Parallelization
Also, like mergesort, quicksort can also be easily parallelized due to its divide-and-conquer nature. Individual in-place partition operations are difficult to parallelize, but once divided, different sections of the list can be sorted in parallel. If we have p processors, we can divide a list of n elements into p sublists in Θ(n) average time, then sort each of these in O((n/p) log(n/p)) average time. Ignoring the O(n) preprocessing, this is linear speedup. Given Θ(n) processors, only O(n) time is required overall.
One advantage of parallel quicksort over other parallel sort algorithms is that no synchronization is required. A new thread is started as soon as a sublist is available for it to work on and it does not communicate with other threads. When all threads complete, the sort is done.
Other more sophisticated parallel sorting algorithms can achieve even better time bounds. For example, in 1991 David Powers described a parallelized quicksort that can operate in O(log n) time given enough processors by performing partitioning implicitly.1
Competitive sorting algorithms
Quicksort is a space-optimized version of the binary tree sort. Instead of inserting items sequentially into an explicit tree, quicksort organizes them concurrently into a tree that is implied by the recursive calls. The algorithms make exactly the same comparisons, but in a different order.
The most direct competitor of quicksort is heapsort. Heapsort is typically somewhat slower than quicksort, but the worst-case running time is always O(n log n). Quicksort is usually faster, though there remains the chance of worst case performance except in the introsort variant. If it's known in advance that heapsort is going to be necessary, using it directly will be faster than waiting for introsort to switch to it. Heapsort also has the important advantage of using only constant additional space (heapsort is in-place), whereas even the best variant of quicksort uses Θ(log n) space. However, heapsort requires efficient random access to be practical.
Quicksort also competes with mergesort, another recursive sort algorithm but with the benefit of worst-case O(n log n) running time. Mergesort is a stable sort, unlike quicksort and heapsort, and can be easily adapted to operate on linked lists and very large lists stored on slow-to-access media such as disk storage or network attached storage. Although quicksort can be written to operate on linked lists, it will often suffer from poor pivot choices without random access. The main disadvantage of mergesort is that it requires Ω(n) auxiliary space in the best case.
Formal analysis
From the initial description it's not obvious that quicksort takes O(n log n) time on average. It's not hard to see that the partition operation, which simply loops over the elements of the array once, uses Θ(n) time. In versions that perform concatenation, this operation is also Θ(n).
In the best case, each time we perform a partition we divide the list into two nearly equal pieces. This means each recursive call processes a list of half the size. Consequently, we can make only log n nested calls before we reach a list of size 1. This means that the depth of the call tree is O(log n). But no two calls at the same level of the call tree process the same part of the original list; thus, each level of calls needs only O(n) time all together (each call has some constant overhead, but since there are only O(n) calls at each level, this is subsumed in the O(n) factor). The result is that the algorithm uses only O(n log n) time.
An alternate approach is to set up a recurrence relation for T(n), the time needed to sort a list of size n. Because a single quicksort call involves O(n) work plus two recursive calls on lists of size n/2 in the best case, the relation would be:
- T(n) = O(n) + 2T(n/2)
Standard mathematical induction techniques for solving this type of relation tell us that T(n) = Θ(n log n).
In fact, it's not necessary to divide the list this precisely; even if each pivot splits the elements with 99% on one side and 1% on the other, the call depth is still limited to 100log n, so the total running time is still O(n log n).
In the worst case, however, the two sublists have size 1 and n-1, and the call tree becomes a linear chain of n nested calls. The ith call does O(n-i) work, and <math>\sum_{i=0}^n (n-i) = O(n^2)<math>. The recurrence relation is:
- T(n) = O(n) + T(1) + T(n - 1) = O(n) + T(n - 1)
This is the same relation as for insertion sort and selection sort, and it solves to T(n) = Θ(n2).
Randomized quicksort expected complexity
Randomized quicksort has the desirable property that it requires only O(n log n) expected time, regardless of the input. But what makes random pivots a good choice?
Suppose we sort the list and then divide it into four parts. The two parts in the middle will contain the best pivots; each of them is larger than at least 25% of the elements and smaller than at least 25% of the elements. If we could consistently choose an element from these two middle parts, we would only have to split the list at most 2log2 n times before reaching lists of size 1, yielding an O(n log n) algorithm.
Unfortunately, a random choice will only choose from these middle parts half the time. The surprising fact is that this is good enough. Imagine that you are flipping a coin over and over until you get k heads. Although this could take a long time, on average only 2k flips are required, and the chance that you won't get k heads after 100k flips is astronomically small. By the same argument, quicksort's recursion will terminate on average at a call depth of only 2(2log2 n). But if its average call depth is O(log n), and each level of the call tree processes at most n elements, the total amount of work done on average is the product, O(n log n).
Average complexity
Even if we aren't able to choose pivots randomly, quicksort still requires only O(n log n) time over all possible permutations of its input. Because this average is simply the sum of the times over all permutations of the input divided by n factorial, it's equivalent to choosing a random permutation of the input. When we do this, the pivot choices are essentially random, leading to an algorithm with the same running time as randomized quicksort.
More precisely, the average number of comparisons over all permutations of the input sequence can be estimated accurately by solving the recurrence relation:
<math>C(n) = n - 1 + \frac{1}{n} \sum_{i=0}^{n-1} (C(i)+C(n-i-1)) = 2n \ln n = 1.39n log_2 n.<math>
Here, n - 1 is the number of comparisons the partition uses. Since the pivot is equally likely to fall anywhere in the sorted list order, the sum is averaging over all possible splits.
This means that, on average, quicksort performs only about 39% worse than the ideal number of comparisons, which is its best case. In this sense it is closer to the best case than the worst case. This fast average runtime is another reason for quicksort's practical dominance over other sorting algorithms.
Space complexity
The space used by quicksort depends on the version used. The version of quicksort with in-place partitioning uses only constant additional space before making any recursive call. However, if it has made O(log n) nested recursive calls, it needs to store a constant amount of information from each of them. Since the best case makes at most O(log n) nested recursive calls, it uses O(log n) space. The worst case makes O(n) nested recursive calls, and so needs O(n) space.
We are eliding a small detail here, however. If we consider sorting arbitrarily large lists, we have to keep in mind that our variables like left and right can no longer be considered to occupy constant space; it takes O(log n) bits to index into a list of n items. Because we have variables like this in every stack frame, in reality quicksort requires O(log2 n) bits of space in the best and average case and O(n log n) space in the worst case. This isn't too terrible, though, since if the list contains mostly distinct elements, the list itself will also occupy O(n log n) bits of space.
The not-in-place version of quicksort uses O(n) space before it even makes any recursive calls. In the best case its space is still limited to O(n), because each level of the recursion uses half as much space as the last, and
- <math>\sum_{i=0}^{\infty} \frac{n}{2^i} = 2n.<math>
Its worst case is dismal, requiring
- <math>\sum_{i=0}^n (n-i+1) = \Theta (n^2)<math>
space, far more than the list itself. If the list elements are not themselves constant size, the problem grows even larger; for example, if most of the list elements are distinct, each would require about O(log n) bits, leading to a best-case O(n log n) and worst-case O(n2 log n) space requirement.
Relationship to selection
A selection algorithm chooses the kth smallest of a list of numbers; this is an easier problem in general than sorting. One simple but effective selection algorithm works nearly in the same manner as quicksort, except that instead of making recursive calls on both sublists, it only makes a single tail-recursive call on the sublist which contains the desired element. This small change lowers the average complexity to linear or Θ(n) time, and makes it an in-place algorithm. A variation on this algorithm brings the worst-case time down to O(n) (see selection algorithm for more information).
Conversely, once we know a worst-case O(n) selection algorithm is available, we can use it to find the ideal pivot (the median) at every step of quicksort, producing a variant with worst-case O(n log n) running time. In practical implementations, however, this variant is considerably slower on average.
Sample implementations
Main article: Quicksort implementations
Here we demonstrate a number of quicksort implementations in various languages. We show only some of the most popular or unique ones here; for additional implementations, see the article quicksort implementations.
C
This sorts an array of integers.
void swap(int *a, int *b) { int t=*a; *a=*b; *b=t; }
void sort(int arr[], int beg, int end)
{
if (end > beg + 1)
{
int piv = arr[beg], l = beg + 1, r = end;
while (l < r)
{
if (arr[l] <= piv)
l++;
else
swap(&arr[l], &arr[--r]);
}
swap(&arr[--l], &arr[beg]);
sort(arr, beg, l);
sort(arr, r, end);
}
}
C++
This is a generic, STL-based version of quicksort.
#include <functional>
#include <algorithm>
#include <iterator>
template< typename BidirectionalIterator, typename Compare >
void quick_sort( BidirectionalIterator first, BidirectionalIterator last, Compare cmp ) {
if( first != last ) {
BidirectionalIterator left = first;
BidirectionalIterator right = last;
BidirectionalIterator pivot = left++;
while( left != right ) {
if( cmp( *left, *pivot ) ) {
++left;
} else {
while( (left != --right) && cmp( *pivot, *right ) )
;
std::iter_swap( left, right );
}
}
--left;
std::iter_swap( first, left );
quick_sort( first, left, cmp );
quick_sort( right, last, cmp );
}
}
template< typename BidirectionalIterator >
inline void quick_sort( BidirectionalIterator first, BidirectionalIterator last ) {
quick_sort( first, last,
std::less_equal< typename std::iterator_traits< BidirectionalIterator >::value_type >()
);
}
Java
import java.util.Comparator;
import java.util.Random;
public class Quicksort {
public static final Random RND = new Random();
private void swap(Object[] array, int i, int j) {
Object tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
private int partition(Object[] array, int begin, int end, Comparator cmp) {
int index = begin + RND.nextInt(end - begin + 1);
Object pivot = array[index];
swap(array, index, end);
for (int i = index = begin; i < end; ++ i) {
if (cmp.compare(array[i], pivot) <= 0) {
swap(array, index++, i);
}
}
swap(array, index, end);
return (index);
}
private void qsort(Object[] array, int begin, int end, Comparator cmp) {
if (end > begin) {
int index = partition(array, begin, end, cmp);
qsort(array, begin, index - 1, cmp);
qsort(array, index + 1, end, cmp);
}
}
public void sort(Object[] array, Comparator cmp) {
qsort(array, 0, array.length - 1, cmp);
}
}
Python
def qsort(L):
if L == []: return []
return qsort([x for x in L[1:] if x< L[0]]) + L[0:1] + \
qsort([x for x in L[1:] if x>=L[0]])
Joy
DEFINE sort == [small][]
[uncons [>] split]
[[swap] dip cons concat] binrec .
PHP
function quicksort($seq) {
if(count($seq)>1) {
$k = $seq[0];
$x = array();
$y = array();
for($i=1; $i<count($seq); $i++) {
if($seq[$i] <= $k) {
$x[] = $seq[$i];
} else {
$y[] = $seq[$i];
}
}
$x = quicksort($x);
$y = quicksort($y);
return array_merge($x, array($k), $y);
} else {
return $seq;
}
}
Haskell
sort :: (Ord a) => [a] -> [a]
sort [] = []
sort (pivot:rest) = sort [y | y <- rest, y < pivot]
++ [pivot] ++
sort [y | y <- rest, y >=pivot]
Prolog
split(H, [A|X], [A|Y], Z) :- order(A, H), split(H, X, Y, Z). split(H, [A|X], Y, [A|Z]) :- not(order(A, H)), split(H, X, Y, Z). split(_, [], [], []). quicksort([], X, X). quicksort([H|T], S, X) :- split(H, T, A, B), quicksort(A, S, [H|Y]), quicksort(B, Y, X).
Ruby
def sort(array)
return [] if array.empty?
left, right = array[1..-1].partition { |y| y <= array.first }
sort(left) + [ array.first ] + sort(right)
end
SML
This example demonstrates the use of an arbitrary predicate in a functional language.
fun quicksort lt lst =
let val rec sort =
fn [] => []
| (x::xs) =>
let
val (left,right) = List.partition (fn y => lt (y, x)) xs
in sort left @ x :: sort right
end
in sort lst
end
External links
- Interactive quicksort (http://pages.stern.nyu.edu/~panos/java/Quicksort/)
References
- Hoare, C. A. R. "Partition: Algorithm 63," "Quicksort: Algorithm 64," and "Find: Algorithm 65." Comm. ACM 4, 321-322, 1961
- R. Sedgewick. Implementing quicksort programs, Communications of the ACM, 21(10):847857, 1978.
- David Musser. Introspective Sorting and Selection Algorithms, Software Practice and Experience vol 27, number 8, pages 983-993, 1997
- A. LaMarca and R. E. Ladner. "The Influence of Caches on the Performance of Sorting." Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997. pp. 370-379.
- Faron Moller. Analysis of Quicksort (http://www.cs.swan.ac.uk/~csfm/CS_332/qsort.pdf). CS 332: Designing Algorithms. Department of Computer Science, University of Wales Swansea.
- Steven Skiena. Lecture 5 - quicksort (http://www.cs.sunysb.edu/~algorith/lectures-good/node5.html). CSE 373/548 - Analysis of Algorithms. Department of Computer Science. SUNY Stony Brook.
Footnotes
1. David M. W. Powers. Parallelized Quicksort with Optimal Speedup (http://citeseer.ist.psu.edu/327487.html). Proceedings of International Conference on Parallel Computing Technologies. Novosibirsk. 1991.de:Quicksortes:Quicksort fr:Tri rapide it:Quicksort he:מיון מהיר lt:Greitojo rūšiavimo algoritmas nl:Quicksort ja:クイックソート pl:Sortowanie szybkie pt:Quicksort sl:Hitro urejanje