Quicksort
From Wikipedia, the free encyclopedia
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 Θ(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. Quicksort is a comparison sort and, in efficient implementations, is not a stable sort.
Contents |
[edit] 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 (the loop invariant).
In simple pseudocode, the algorithm might be expressed as:
function quicksort(q)
var list less, pivotList, greater
if length(q) ≤ 1
return q
select a pivot value pivot from q
for each x in q 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))
Notice that we only examine elements by comparing them to other elements. This makes quicksort a comparison sort.
[edit] 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 (see big-O notation for the meaning of Ω). 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 form of the partition algorithm is not the original form; multiple variations can be found in various textbooks, such as versions not having the storeIndex. However, this form is probably the easiest to understand.
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 or equal to a[pivotIndex] to the beginning of the subarray, leaving all the greater 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.
Below is the basic quick sort algorithm written in C.
void quickSort(int numbers[], int array_size)
{
q_sort(numbers, 0, array_size - 1);
}
void q_sort(int numbers[], int left, int right)
{
int l_hold = left;
int r_hold = right;
int pivot = numbers[left];
while (left < right)
{
while ((numbers[right] >= pivot) && (left < right))
right--;
if (left != right)
{
numbers[left] = numbers[right];
left++;
}
while ((numbers[left] <= pivot) && (left < right))
left++;
if (left != right)
{
numbers[right] = numbers[left];
right--;
}
}
numbers[left] = pivot;
pivot = left;
left = l_hold;
right = r_hold;
if (left < pivot)
q_sort(numbers, left, pivot-1);
if (right > pivot)
q_sort(numbers, pivot+1, right);
}
[edit] 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 Θ(log n) additional stack space on average in recursive implementations and Θ(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 pivot choice, such as always choosing the first element, will be terribly inefficient for certain inputs. For example, if the input is already sorted, a common practical case, always choosing the first element as the pivot causes quicksort to degenerate into a selection sort with Θ(n2) running time. When using the simplest variant, the recursion depth also becomes linear, requiring Θ(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. The average number of comparisons scales as 2n log n, to leading order; in contrast the ideal number of comparisons is log n!/log 2 
[1].
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.
[edit] 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. One defense against this is to use highly unpredictable random seeds, such as numbers generated from hardware random number generators or entropy pools, and to avoid exposing partial information that might reveal information about the random seed or sequence.
Another choice is to select the median of the first, middle and last elements as the pivot. Adding two randomly selected elements resists chosen data attacks. 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 time can be reduced to O(n log n). 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.
[edit] 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, and the pseudocode implementations presented in this article are consistent with this.
[edit] Other optimizations
[edit] Using different algorithms for small lists
Another optimization is to switch to a different sorting algorithm once the list becomes small, perhaps ten or fewer 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, found in the 1997 Microsoft C library, used a cutoff of 8 elements before switching to selection 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.
An algorithm that has been found to work particularly well for realtime execution speedups of quicksort is to use Comb sort when the partitions can be completely contained in the L1 data cache. This is usually 4K to 8K and possibly more if larger cache is available. A partition with less than 40 entries is not processed at all until the very end. With the min and max instructions available on current processors for most primitive types, it is possible to implement Comb sort without any branching other than the looping. A final Insertion sort pass on the entire list will be insignificant compared to the rest of the algorithm, but will sort any remaining out of place entries. Alternatively, Insertion sort can be used at the end of processing each partition (for small partitions and immediately after Comb sort). Comb sort with clever use of low level vector operations by finding out the min and max of 4 vectors at a time (but outputting 2 vectors only, min and max, at a time) while shuffling one vector (or two in opposite directions) every iteration, a shrink factor of 1.6 (vs. 1.3) can be used further improving performance. Because all items in every partition are in the cache, Shell sort may also prove to show some speed gains.
[edit] Limiting worst-case memory usage
The straightforward approach to dealing with the two partitions is to apply QuickSort to the first (left) partition, thereby deferring action on the second partition. This choice will be made again at the next level down. Unfortunate choices of the partition element at each level might partition each sequence of length n into partitions of at worst length (n - 1) and 1, thus requiring a recursion depth of N - 1 in sorting N elements; disastrous for large N. A simple way to avoid this is instead to defer action on the larger partition, proceeding with QuickSort on the smaller partition which can be no more than half the size of the interval. This limits the recursion depth of quicksort to Θ(log n); even for huge lists, this variant typically requires no more than roughly 100 words of memory. Specifically, if a 32-bit integer were sufficient to index the elements of the array being sorted, the recursion depth would be limited to 32. 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)
leftSize := (pivotNewIndex-1) - left + 1
rightSize := right - (pivotNewIndex + 1) + 1
if leftSize < rightSize
quicksort(a, left, pivotNewIndex-1)
left := pivotNewIndex+1
else
quicksort(a, pivotNewIndex+1, right)
right := pivotNewIndex-1
[edit] Iterative version
Explicit recursion can be avoided using an iterative form of quicksort that replaces the call stack by an explicit stack data structure. Although this does not make the algorithm use asymptotically less time or space, the practical advantage lies in avoiding the time and space overhead of subroutine entry and exit that occurs during general recursive calls. The disadvantage is of considerably greater code complexity. A simpler in-place sort of competitive speed is heapsort.
// A is an array to be sorted for elements First to Last inclusive.
// v is a variable of type corresponding to the sort key of array A.
// sp is a stack pointer to a small local data structure used by Push and Pop.
// something like local arrays SaveA(32), SaveB(32) of the same type as L and R,
// where Push(x,y); means sp:=sp + 1; SaveA(sp):=x; SaveB(sp):=y;
// and Pop(x,y); means x:=SaveA(sp); y:=SaveB(sp); sp:=sp - 1;
// var L,L2,p,r,r2: longint; of a type equivalent to First and Last.
QuickSort(A,First,Last)
{ var v,sp,L,L2,p,r,r2;
sp=0; // Mark the local stack as empty.
Push(First,Last); // Loads First and Last onto the stack
while( sp > 0 )
{ Pop(L, r)/2;
while( L < r) // span is L:r
{ p = (L+r)/2;
v = A[p].key; // the value must not stay in the array!
L2 = L;
r2 = r;
while( L2 < r2 ) // repeat until L2 >= r2
{ while( A[L2].key < v ) // scan left partition
{ L2 = L2+L;
}
while( A[r2].key > v ) // scan right partition
{ r2 = r2-L;
}
if(L2 <= r2 )
{ if(L2 equals r2)
{ Swap(A[L2],A[r2]);
}
L2 = L2 + L;
r2 = r2 - L;
}
}
if(r2-L > r-L2) // is left side piece larger?
{ if(L<r2)
{ Push(L,r2);
}
L = L2;
}
else // if left side isn't, right side is larger
{ if(L2 < r)
{ Push(L2,r);
r = r2;
}
}
} // end while( L < r )
} // end while( sp>0 )
} // end QuickSort
Which is indeed more complicated. Extensions might include a median-of-three selection of the pivot (with re-ordering during that selection), and the use of InsertionSort for any partition less than (say) eight elements in length.
[edit] Parallelization
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
[edit] 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, when operating on arrays, it requires Ω(n) auxiliary space in the best case, whereas the variant of quicksort with in-place partitioning and tail recursion uses only O(log n) space. (Note that when operating on linked lists, mergesort only requires a small, constant amount of auxiliary storage.)
[edit] 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)
The master theorem tells 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 (or any other fixed fraction), 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 
. 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).
[edit] 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 infinitesimally 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).
[edit] 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:
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.
C(n)= (n-1) + C(n/2) + C(n/2)
= (n-1) + 2C(n/2)
= (n-1) + 2((n/2) - 1 + C(n/4))
= n + n + 4C(n/4) - 1 - 2
= n + n + n + 8C(n/8) - 1 - 2- 4
= kn + 2^kC(n/(2^k)) - (1 + 2 + 3 + . . . . . + 2^(k-1))
where n>k>0
=
[edit] 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
Its worst case is dismal, requiring
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.
[edit] 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.
[edit] External links
- Quicksort
- Quicksort Java Applet
- Multidimensional quicksort in Java
- Efficient quicksort implementation in C, available under a liberal license
- Literate implementations of Quicksort in various languages on LiteratePrograms
- Non-recursive, C implementation of Quicksort with diagrams
- Fast Sorting with Quicksort: Comprehensive guide with detailed explanations, code, and walkthrough. on kirupa.com
[edit] References
- Brian C. Dean, "A Simple Expected Running Time Analysis for Randomized 'Divide and Conquer' Algorithms." Discrete Applied Mathematics 154(1): 1-5. 2006.
- 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, Comm. ACM, 21(10):847-857, 1978.
- David Musser. Introspective Sorting and Selection Algorithms, Software Practice and Experience vol 27, number 8, pages 983-993, 1997
- Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0. Pages 113–122 of section 5.2.2: Sorting by Exchanging.
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 7: Quicksort, pp.145–164.
- 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. CS 332: Designing Algorithms. Department of Computer Science, University of Wales Swansea.
- Steven Skiena. Lecture 5 - quicksort. CSE 373/548 - Analysis of Algorithms. Department of Computer Science. State University of New York at Stony Brook.
[edit] Footnotes
1. David M. W. Powers. Parallelized Quicksort with Optimal Speedup. Proceedings of International Conference on Parallel Computing Technologies. Novosibirsk. 1991.
