 Animated visualization of the quicksort algorithm. The horizontal lines are pivot values. | |
| Class | Sorting algorithm |
|---|---|
| Worst-caseperformance | |
| Best-caseperformance | (simple partition) or (three-way partition and equal keys) |
| Averageperformance | |
| Worst-casespace complexity | auxiliary (naive) auxiliary (Hoare 1962) |
| Optimal | No |
Quicksort is an efficient, general-purposesorting algorithm. Quicksort was developed by British computer scientistTony Hoare in 1959[1] and published in 1961.[2] It is still a commonly used algorithm for sorting. Overall, it is slightly faster thanmerge sort andheapsort for randomized data, particularly on larger distributions.[3]
Quicksort is adivide-and-conquer algorithm. It works by selecting a "pivot" element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. For this reason, it is sometimes calledpartition-exchange sort.[4] The sub-arrays are then sortedrecursively. This can be donein-place, requiring small additional amounts ofmemory to perform the sorting.
Quicksort is acomparison sort, meaning that it can sort items of any type for which a "less-than" relation (formally, atotal order) is defined. It is a comparison-based sort since elementsa andb are only swapped in case their relative order has been obtained in the transitive closure of prior comparison-outcomes. Most implementations of quicksort are notstable, meaning that the relative order of equal sort items is not preserved.
Mathematical analysis of quicksort shows that,on average, the algorithm takes comparisons to sortn items. In theworst case, it makes comparisons.
The quicksort algorithm was developed in 1959 byTony Hoare while he was a visiting student atMoscow State University. At that time, Hoare was working on amachine translation project for theNational Physical Laboratory. As a part of the translation process, he needed to sort the words in Russian sentences before looking them up in a Russian-English dictionary, which was in alphabetical order onmagnetic tape.[5] After recognizing that his first idea,insertion sort, would be slow, he came up with a new idea. He wrote the partition part in MercuryAutocode but had trouble dealing with the list of unsorted segments. On return to England, he was asked to write code forShellsort. Hoare mentioned to his boss that he knew of a faster algorithm and his boss bet asixpence that he did not. His boss ultimately accepted that he had lost the bet. Hoare published a paper about his algorithm inThe Computer JournalVolume 5, Issue 1, 1962, Pages 10–16. Later, Hoare learned aboutALGOL and its ability to do recursion, which enabled him to publish an improved version of the algorithm in ALGOL inCommunications of the Association for Computing Machinery, the premier computer science journal of the time.[2][6] The ALGOL code is published inCommunications of the ACM (CACM), Volume 4, Issue 7 July 1961, pp 321 Algorithm 63: partition and Algorithm 64: Quicksort.
Quicksort gained widespread adoption, appearing, for example, inUnix as the default library sort subroutine. Hence, it lent its name to theC standard library subroutineqsort[7] and in the reference implementation ofJava.
Robert Sedgewick's PhD thesis in 1975 is considered a milestone in the study of Quicksort where he resolved many open problems related to the analysis of various pivot selection schemes includingSamplesort, adaptive partitioning by Van Emden[8] as well as derivation of expected number of comparisons and swaps.[7]Jon Bentley andDoug McIlroy in 1993 incorporated various improvements for use in programming libraries, including a technique to deal with equal elements and a pivot scheme known aspseudomedian of nine, where a sample of nine elements is divided into groups of three and then the median of the three medians from three groups is chosen.[7] Bentley described another simpler and compact partitioning scheme in his bookProgramming Pearls that he attributed toNico Lomuto. Later Bentley wrote that he used Hoare's version for years but never really understood it but Lomuto's version was simple enough to prove correct.[9] Bentley described Quicksort as the "most beautiful code I had ever written" in the same essay. Lomuto's partition scheme was also popularized by the textbookIntroduction to Algorithms although it is inferior to Hoare's scheme because it does three times more swaps on average and degrades toO(n2) runtime when all elements are equal.[10][self-published source?] McIlroy would further produce anAntiQuicksort (aqsort) function in 1998, which consistently drives even his 1993 variant of Quicksort into quadratic behavior by producing adversarial data on-the-fly.[11]
Quicksort is a type ofdivide-and-conquer algorithm for sorting an array, based on a partitioning routine; the details of this partitioning can vary somewhat, so that quicksort is really a family of closely related algorithms. Applied to a range of at least two elements, partitioning produces a division into two consecutive non empty sub-ranges, in such a way that no element of the first sub-range is greater than any element of the second sub-range. After applying this partition, quicksort then recursively sorts the sub-ranges, possibly after excluding from them an element at the point of division that is at this point known to be already in its final location. Due to its recursive nature, quicksort (like the partition routine) has to be formulated so as to be callable for a range within a larger array, even if the ultimate goal is to sort a complete array. The steps forin-place quicksort are:
The choice of partition routine (including the pivot selection) and other details not entirely specified above can affect the algorithm's performance, possibly to a great extent for specific input arrays. In discussing the efficiency of quicksort, it is therefore necessary to specify these choices first. Here we mention two specific partition methods.
This scheme is attributed to Nico Lomuto and popularized by Bentley in his bookProgramming Pearls[12] and Cormenet al. in their bookIntroduction to Algorithms.[13] In most formulations this scheme chooses as the pivot the last element in the array. The algorithm maintains indexi as it scans the array using another indexj such that the elements atlo throughi-1 (inclusive) are less than the pivot, and the elements ati throughj (inclusive) are equal to or greater than the pivot. As this scheme is more compact and easy to understand, it is frequently used in introductory material, although it is less efficient than Hoare's original scheme e.g., when all elements are equal.[14] The complexity of Quicksort with this scheme degrades toO(n2) when the array is already in order, due to the partition being the worst possible one.[10] There have been various variants proposed to boost performance including various ways to select the pivot, deal with equal elements, use other sorting algorithms such asinsertion sort for small arrays, and so on. Inpseudocode, a quicksort that sorts elements atlo throughhi (inclusive) of an arrayA can be expressed as:[13]
// Sorts (a portion of) an array, divides it into partitions, then sorts thosealgorithm quicksort(A, lo, hi)is// Ensure indices are in correct orderif lo >= hi || lo < 0then return// Partition array and get the pivot index p := partition(A, lo, hi)// Sort the two partitions quicksort(A, lo, p - 1)// Left side of pivot quicksort(A, p + 1, hi)// Right side of pivot// Divides array into two partitionsalgorithm partition(A, lo, hi)is pivot := A[hi]// Choose the last element as the pivot// Temporary pivot index i := lofor j := loto hi - 1do// If the current element is less than or equal to the pivotif A[j] <= pivotthen// Swap the current element with the element at the temporary pivot index swap A[i]with A[j]// Move the temporary pivot index forward i := i + 1// Swap the pivot with the last element swap A[i]with A[hi]return i// the pivot index
Sorting the entire array is accomplished byquicksort(A, 0, length(A) - 1).
i andj respectively), the black outlines show the positions of the sorted elements, and the filled black square shows the value that is being compared to (pivot).The original partition scheme described byTony Hoare uses two pointers (indices into the range) that start at both ends of the array being partitioned, then move toward each other, until they detect an inversion: a pair of elements, one greater than the pivot at the first pointer, and one less than the pivot at the second pointer; if at this point the first pointer is still before the second, these elements are in the wrong order relative to each other, and they are then exchanged.[15] After this the pointers are moved inwards, and the search for an inversion is repeated; when eventually the pointers cross (the first points after the second), no exchange is performed; a valid partition is found, with the point of division between the crossed pointers (any entries that might be strictly between the crossed pointers are equal to the pivot and can be excluded from both sub-ranges formed). With this formulation it is possible that one sub-range turns out to be the whole original range, which would prevent the algorithm from advancing. Hoare therefore stipulates that at the end, the sub-range containing the pivot element (which still is at its original position) can be decreased in size by excluding that pivot, after (if necessary) exchanging it with the sub-range element closest to the separation; thus, termination of quicksort is ensured.
With respect to this original description, implementations often make minor but important variations. Notably, the scheme as presented below includes elements equal to the pivot among the candidates for an inversion (so "greater than or equal" and "less than or equal" tests are used instead of "greater than" and "less than" respectively; since the formulation usesdo...while rather thanrepeat...until which is actually reflected by the use of strict comparison operators[clarification needed]). While there is no reason to exchange elements equal to the pivot, this change allows tests on the pointers themselves to be omitted, which are otherwise needed to ensure they do not run out of range. Indeed, since at least one instance of the pivot value is present in the range, the first advancement of either pointer cannot pass across this instance if an inclusive test is used; once an exchange is performed, these exchanged elements are now both strictly ahead of the pointer that found them, preventing that pointer from running off. (The latter is true independently of the test used, so it would be possible to use the inclusive test only when looking for the first inversion. However, using an inclusive test throughout also ensures that a division near the middle is found when all elements in the range are equal, which gives an important efficiency gain for sorting arrays with many equal elements.) The risk of producing a non-advancing separation is avoided in a different manner than described by Hoare. Such a separation can only result when no inversions are found, with both pointers advancing to the pivot element at the first iteration (they are then considered to have crossed, and no exchange takes place).
// Sorts (a portion of) an array, divides it into partitions, then sorts thosealgorithm quicksort(A, lo, hi)isif lo >= 0 && hi >= 0 && lo < hithen p := partition(A, lo, hi) quicksort(A, lo, p) // Note: the pivot is now included quicksort(A, p + 1, hi)// Divides array into two partitionsalgorithm partition(A, lo, hi)is// Pivot value pivot := A[lo]// Choose the first element as the pivot// Left index i := lo - 1// Right index j := hi + 1loop forever// Move the left index to the right at least once and while the element at// the left index is less than the pivotdo i := i + 1while A[i] < pivot// Move the right index to the left at least once and while the element at// the right index is greater than the pivotdo j := j - 1while A[j] > pivot// If the indices crossed, returnif i >= jthenreturn j// Swap the elements at the left and right indicesswap A[i]with A[j]
The entire array is sorted byquicksort(A, 0, length(A) - 1).
Hoare's scheme is more efficient than Lomuto's partition scheme because it does three times fewer swaps on average. Also, as mentioned, the implementation given creates a balanced partition even when all values are equal.[10][self-published source?], which Lomuto's scheme does not. Like Lomuto's partition scheme, Hoare's partitioning also would cause Quicksort to degrade toO(n2) for already sorted input, if the pivot was chosen as the first or the last element. With the middle element as the pivot, however, sorted data results with (almost) no swaps in equally sized partitions leading to best case behavior of Quicksort, i.e.O(n log(n)). Like others, Hoare's partitioning doesn't produce a stable sort. In this scheme, the pivot's final location is not necessarily at the index that is returned, as the pivot and elements equal to the pivot can end up anywhere within the partition after a partition step, and may not be sorted until the base case of a partition with a single element is reached via recursion. Therefore, the next two segments that the main algorithm recurs on are(lo..p) (elements ≤ pivot) and(p+1..hi) (elements ≥ pivot) as opposed to(lo..p-1) and(p+1..hi) as in Lomuto's scheme.
Subsequent recursions (expansion on previous paragraph)
Let's expand a little bit on the next two segments that the main algorithm recurs on. Because we are using strict comparators (>, <) in the"do...while" loops to prevent ourselves from running out of range, there's a chance that the pivot itself gets swapped with other elements in the partition function. Therefore,the index returned in the partition function isn't necessarily where the actual pivot is. Consider the example of[5, 2, 3, 1, 0], following the scheme, after the first partition the array becomes[0, 2, 1, 3, 5], the "index" returned is 2, which is the number 1, when the real pivot, the one we chose to start the partition with was the number 3. With this example, we see how it is necessary to include the returned index of the partition function in our subsequent recursions. As a result, we are presented with the choices of either recursing on(lo..p) and(p+1..hi), or(lo..p-1) and(p..hi). Which of the two options we choose depends on which index (i orj) we return in the partition function when the indices cross, and how we choose our pivot in the partition function (floor v.s.ceiling).
First examine the choice of recursing on(lo..p) and(p+1..hi), with the example of sorting an array where multiple identical elements exist[0, 0]. If index i (the "latter" index) is returned after indices cross in the partition function, the index 1 would be returned after the first partition. The subsequent recursion on(lo..p) would be on (0, 1), which corresponds to the same array[0, 0]. A non-advancing separation that causes infinite recursion is produced. It is therefore obvious thatwhen recursing on(lo..p) and(p+1..hi), because the left half of the recursion includes the returned index, it is the partition function's job to exclude the "tail" in non-advancing scenarios. Which is to say, index j (the "former" index when indices cross) should be returned instead of i. Going with a similar logic, when considering the example of an already sorted array[0, 1], the choice of pivot needs to be "floor" to ensure that the pointers stop on the "former" instead of the "latter" (with "ceiling" as the pivot, the index 1 would be returned and included in(lo..p) causing infinite recursion). It is for the same reason why choice of the last element as pivot must be avoided.
The choice of recursing on(lo..p-1) and(p..hi) follows the same logic as above.Because the right half of the recursion includes the returned index, it is the partition function's job to exclude the "head" in non-advancing scenarios. The index i (the "latter" index after the indices cross) in the partition function needs to be returned, and "ceiling" needs to be chosen as the pivot. The two nuances are clear, again, when considering the examples of sorting an array where multiple identical elements exist ([0, 0]), and an already sorted array[0, 1] respectively. It is noteworthy that with version of recursion, for the same reason, choice of the first element as pivot must be avoided.
In the very early versions of quicksort, the leftmost element of the partition would often be chosen as the pivot element. Unfortunately, this causes worst-case behavior on already sorted arrays, which is a rather common use-case.[16] The problem was easily solved by choosing either a random index for the pivot, choosing the middle index of the partition or (especially for longer partitions) choosing themedian of the first, middle and last element of the partition for the pivot (as recommended bySedgewick).[17] This "median-of-three" rule counters the case of sorted (or reverse-sorted) input, and gives a better estimate of the optimal pivot (the true median) than selecting any single element, when no information about the ordering of the input is known.
Median-of-three code snippet for Lomuto partition:
mid := ⌊(lo + hi) / 2⌋if A[mid] < A[lo] swap A[lo] with A[mid]if A[hi] < A[lo] swap A[lo] with A[hi]if A[mid] < A[hi] swap A[mid] with A[hi]pivot := A[hi]
It puts a median intoA[hi] first, then that new value ofA[hi] is used for a pivot, as in a basic algorithm presented above.
Specifically, the expected number of comparisons needed to sortn elements (see§ Average-case analysis) with random pivot selection is1.386n logn. Median-of-three pivoting brings this down toCn, 2 ≈ 1.188n logn, at the expense of a three-percent increase in the expected number of swaps.[7] An even stronger pivoting rule, for larger arrays, is to pick theninther, a recursive median-of-three (Mo3), defined as[7]
Selecting a pivot element is also complicated by the existence ofinteger overflow. If the boundary indices of the subarray being sorted are sufficiently large, the naïve expression for the middle index,(lo +hi)/2, will cause overflow and provide an invalid pivot index. This can be overcome by using, for example,lo + (hi−lo)/2 to index the middle element, at the cost of more complex arithmetic. Similar issues arise in some other methods of selecting the pivot element.
With a partitioning algorithm such as the Lomuto partition scheme described above (even one that chooses good pivot values), quicksort exhibits poor performance for inputs that contain many repeated elements. The problem is clearly apparent when all the input elements are equal: at each recursion, the left partition is empty (no input values are less than the pivot), and the right partition has only decreased by one element (the pivot is removed). Consequently, the Lomuto partition scheme takesquadratic time to sort an array of equal values. However, with a partitioning algorithm such as the Hoare partition scheme, repeated elements generally results in better partitioning, and although needless swaps of elements equal to the pivot may occur, the running time generally decreases as the number of repeated elements increases (with memory cache reducing the swap overhead). In the case where all elements are equal, Hoare partition scheme needlessly swaps elements, but the partitioning itself is best case, as noted in the Hoare partition section above.
To solve the Lomuto partition scheme problem (sometimes called theDutch national flag problem[7]), an alternative linear-time partition routine can be used that separates the values into three groups: values less than the pivot, values equal to the pivot, and values greater than the pivot. (Bentley and McIlroy call this a "fat partition" and it was already implemented in theqsort ofVersion 7 Unix.[7]) The values equal to the pivot are already sorted, so only the less-than and greater-than partitions need to be recursively sorted. In pseudocode, the quicksort algorithm becomes:
// Sorts (a portion of) an array, divides it into partitions, then sorts thosealgorithm quicksort(A, lo, hi)isif lo >= 0 && lo < hithen lt, gt := partition(A, lo, hi)// Multiple return values quicksort(A, lo, lt - 1) quicksort(A, gt + 1, hi)// Divides array into three partitionsalgorithm partition(A, lo, hi)is// Pivot value pivot := A[(lo + hi) / 2]// Choose the middle element as the pivot (integer division)// Lesser, equal and greater index lt := lo eq := lo gt := hi// Iterate and compare all elements with the pivotwhile eq <= gtdoif A[eq] < pivotthen// Swap the elements at the equal and lesser indicesswap A[eq]with A[lt]// Increase lesser index lt := lt + 1// Increase equal index eq := eq + 1elseif A[eq] > pivotthen// Swap the elements at the equal and greater indicesswap A[eq]with A[gt]// Decrease greater index gt := gt - 1else//if A[eq] = pivotthen// Increase equal index eq := eq + 1// Return lesser and greater indicesreturn lt, gt
Thepartition algorithm returns indices to the first ('leftmost') and to the last ('rightmost') item of the middle partition. Every other item of the partition is equal to the pivot and is therefore sorted. Consequently, the items of the partition need not be included in the recursive calls toquicksort.
The best case for the algorithm now occurs when all elements are equal (or are chosen from a small set ofk ≪n elements). In the case of all equal elements, the modified quicksort will perform only two recursive calls on empty subarrays and thus finish in linear time (assuming thepartition subroutine takes no longer than linear time).
Other important optimizations, also suggested by Sedgewick and widely used in practice, are:[18][19]
Quicksort's divide-and-conquer formulation makes it amenable toparallelization usingtask parallelism. The partitioning step is accomplished through the use of aparallel prefix sum algorithm to compute an index for each array element in its section of the partitioned array.[22][23] Given an array of sizen, the partitioning step performsO(n) work inO(logn) time and requiresO(n) additional scratch space. After the array has been partitioned, the two partitions can be sorted recursively in parallel. Assuming an ideal choice of pivots, parallel quicksort sorts an array of sizen inO(n logn) work inO(log2n) time usingO(n) additional space.
Quicksort has some disadvantages when compared to alternative sorting algorithms, likemerge sort, which complicate its efficient parallelization. The depth of quicksort's divide-and-conquer tree directly impacts the algorithm's scalability, and this depth is highly dependent on the algorithm's choice of pivot. Additionally, it is difficult to parallelize the partitioning step efficiently in-place. The use of scratch space simplifies the partitioning step, but increases the algorithm'smemory footprint and constant overheads.
Other more sophisticated parallel sorting algorithms can achieve even better time bounds.[24] For example, in 1991David M W Powers described a parallelized quicksort (and a relatedradix sort) that can operate inO(logn) time on aCRCW (concurrent read and concurrent write)PRAM (parallelrandom-access machine) withn processors by performing partitioning implicitly.[25]
The most unbalanced partition occurs when one of the sublists returned by the partitioning routine is of sizen − 1.[26] This may occur if the pivot happens to be the smallest or largest element in the list, or in some implementations (e.g., the Lomuto partition scheme as described above) when all the elements are equal.
If this happens repeatedly in every partition, then each recursive call processes a list of size one less than the previous list. Consequently, it takesn − 1 nested calls before to reach a list of size 1. This means that thecall tree is a linear chain ofn − 1 nested calls. Theith call doesO(n −i) work to do the partition, and, so in that case quicksort takesO(n2) time.
In the most balanced case, each partition divides the list into two nearly equal pieces. This means each recursive call processes a list of half the size. Consequently, onlylog2n nested calls can be made before reaching a list of size 1. This means that the depth of thecall tree islog2n. 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 onlyO(n) time all together (each call has some constant overhead, but since there are onlyO(n) calls at each level, this is subsumed in theO(n) factor). The result is that the algorithm uses onlyO(n logn) time.
To sort an array ofn distinct elements, quicksort takesO(n logn) time in expectation, averaged over alln! permutations ofn elements withequal probability. Alternatively, if the algorithm selects the pivot uniformly at random from the input array, the same analysis can be used to bound the expected running time for any input sequence; the expectation is then taken over the random choices made by the algorithm (Cormenet al.,Introduction to Algorithms,[13] Section 7.3).
Three common proofs to this claim use percentiles, recurrences, and binary search trees, each providing different insights into quicksort's workings.
If each pivot has rank somewhere in the middle 50 percent, that is, between the 25thpercentile and the 75th percentile, then it splits the elements with at least 25% and at most 75% on each side. Consistently choosing such pivots would only have to split the list at most times before reaching lists of size 1, yielding anO(n logn) algorithm.
When the input is arandom permutation, the pivot has a random rank, and so it is not guaranteed to be in the middle 50 percent. However, when starting from a random permutation, each recursive call's pivot has a random rank in its list, and therefore is in the middle 50 percent approximately half the time. Imagine that a coin is flipped: heads means that the rank of the pivot is in the middle 50 percent, tail means that it isn't. Now imagine that the coin is flipped over and over until it getsk heads. Although this could take a long time, on average only2k flips are required, and the chance that the coin won't getk heads after100k flips is highly improbable (this can be made rigorous usingChernoff bounds). By the same argument, Quicksort's recursion will terminate on average at a call depth of only. But if its average call depth isO(logn), and each level of the call tree processes at mostn elements, the total amount of work done on average is the product,O(n logn). The algorithm does not have to verify that the pivot is in the middle half as long as it is a consistent amount of times.
Using more careful arguments, it is possible to extend this proof, for the version of Quicksort where the pivot is randomly chosen,to show a time bound that holdswith high probability: specifically, for any given, let, then with probability at least, the number of comparisons will not exceed.[27]
An alternative approach is to set up arecurrence relation for theT(n) factor, the time needed to sort a list of sizen. In the most unbalanced case, a single quicksort call involvesO(n) work plus two recursive calls on lists of size0 andn−1, so the recurrence relation is
This is the same relation as forinsertion sort andselection sort, and it solves to worst caseT(n) =O(n2).
In the most balanced case, a single quicksort call involvesO(n) work plus two recursive calls on lists of sizen/2, so the recurrence relation is
Themaster theorem for divide-and-conquer recurrences tells us thatT(n) =O(n logn).
The outline of a formal proof of theO(n logn) expected time complexity follows. Assume that there are no duplicates as duplicates could be handled with linear time pre- and post-processing, or considered cases easier than the analyzed. When the input is a random permutation, the rank of the pivot is uniform random from 0 ton − 1. Then the resulting parts of the partition have sizesi andn −i − 1, and i is uniform random from 0 ton − 1. So, averaging over all possible splits and noting that the number of comparisons for the partition isn − 1, the average number of comparisons over all permutations of the input sequence can be estimated accurately by solving the recurrence relation:
Solving the recurrence givesC(n) = 2n lnn ≈ 1.39n log2n.
This means that, on average, quicksort performs only about 39% worse than in its best case. In this sense, it is closer to the best case than the worst case. Acomparison sort cannot use less thanlog2(n!) comparisons on average to sortn items (asexplained in the article Comparison sort) and in case of largen,Stirling's approximation yieldslog2(n!) ≈n(log2n − log2e), so quicksort is not much worse than an ideal comparison sort. This fast average runtime is another reason for quicksort's practical dominance over other sorting algorithms.
The followingbinary search tree (BST) corresponds to each execution of quicksort: the initial pivot is the root node; the pivot of the left half is the root of the left subtree, the pivot of the right half is the root of the right subtree, and so on. The number of comparisons of the execution of quicksort equals the number of comparisons during the construction of the BST by a sequence of insertions. So, the average number of comparisons for randomized quicksort equals the average cost of constructing a BST when the values inserted form a random permutation.
Consider a BST created by insertion of a sequence of values forming a random permutation. LetC denote the cost of creation of the BST. We have, where is a binary random variable expressing whether during the insertion of there was a comparison to.
Bylinearity of expectation, the expected value ofC is.
Fixi andj<i. The values, once sorted, definej+1 intervals. The core structural observation is that is compared to in the algorithm if and only if falls inside one of the two intervals adjacent to.
Observe that since is a random permutation, is also a random permutation, so the probability that is adjacent to is exactly.
Simplified as the short calculation:
The space used by quicksort depends on the version used.
The in-place version of quicksort has a space complexity ofO(logn), even in the worst case, when it is carefully implemented using the following strategies.
Quicksort with in-place and unstable partitioning uses only constant additional space before making any recursive call. Quicksort must store a constant amount of information for each nested recursive call. Since the best case makes at mostO(logn) nested recursive calls, it usesO(logn) space. However, without Sedgewick's trick to limit the recursive calls, in the worst case quicksort could makeO(n) nested recursive calls and needO(n) auxiliary space.
From a bit complexity viewpoint, variables such aslo andhi do not use constant space; it takesO(logn) bits to index into a list ofn items. Because there are such variables in every stack frame, quicksort using Sedgewick's trick requiresO((logn)2) bits of space. This space requirement isn't too terrible, though, since if the list contained distinct elements, it would need at leastO(n logn) bits of space.
Stack-free versions of Quicksort have been proposed. These use additional space (more precisely, one cell of the type of the sorted records, in order to exchange records, and a constant number of integer variables used as indices).[28]
Another, less common, not-in-place, version of quicksort[citation needed] usesO(n) space for working storage and can implement a stable sort. The working storage allows the input array to be easily partitioned in a stable manner and then copied back to the input array for successive recursive calls. Sedgewick's optimization is still appropriate.
Quicksort is a space-optimized version of thebinary 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. An often desirable property of asorting algorithm is stability – that is the order of elements that compare equal is not changed, allowing controlling order of multikey tables (e.g. directory or folder listings) in a natural way. This property is hard to maintain for in-place quicksort (that uses only constant additional space for pointers and buffers, andO(logn) additional space for the management of explicit or implicit recursion). For variant quicksorts involving extra memory due to representations using pointers (e.g. lists or trees) or files (effectively lists), it is trivial to maintain stability. The more complex, or disk-bound, data structures tend to increase time cost, in general making increasing use of virtual memory or disk.
The most direct competitor of quicksort isheapsort. Heapsort has the advantages of simplicity, and a worst case run time ofO(n logn), but heapsort'saverage running time is usually considered slower than in-place quicksort, primarily due to its worselocality of reference.[29] This result is debatable; some publications indicate the opposite.[30][31] The main disadvantage of quicksort is the implementation complexity required to avoid bad pivot choices and the resultantO(n2) performance.Introsort is a variant of quicksort which solves this problem by switching to heapsort when a bad case is detected. Major programming languages, such as C++ (in the GNU and LLVM implementations), use introsort.[32]
Quicksort also competes withmerge sort, anotherO(n logn) sorting algorithm. Merge sort's main advantages are that it is astable sort and has excellent worst-case performance. The main disadvantage of merge sort is that it is an out-of-place algorithm, so when operating on arrays, efficient implementations requireO(n) auxiliary space (vs.O(logn) for quicksort with in-place partitioning and tail recursion, orO(1) for heapsort).
Merge sort works very well onlinked lists, requiring only a small, constant amount of auxiliary storage. Although quicksortcan be implemented as a stable sort using linked lists, there is no reason to; it will often suffer from poor pivot choices without random access, and is essentially always inferior to merge sort. Merge sort is also the algorithm of choice forexternal sorting of very large data sets stored on slow-to-access media such asdisk storage ornetwork-attached storage.
Bucket sort with two buckets is very similar to quicksort; the pivot in this case is effectively the value in the middle of the value range, which does well on average for uniformly distributed inputs.
Aselection algorithm chooses thekth 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, and is accordingly known asquickselect. The difference is that instead of making recursive calls on both sublists, it only makes a single tail-recursive call on the sublist that contains the desired element. This change lowers the average complexity to linear orO(n) time, which is optimal for selection, but the selection algorithm is stillO(n2) in the worst case.
A variant of quickselect, themedian of medians algorithm, chooses pivots more carefully, ensuring that the pivots are near the middle of the data (between the 30th and 70th percentiles), and thus has guaranteed linear time –O(n). This same pivot strategy can be used to construct a variant of quicksort (median of medians quicksort) withO(n logn) time. However, the overhead of choosing the pivot is significant, so this is generally not used in practice.
More abstractly, given anO(n) selection algorithm, one can use it to find the ideal pivot (the median) at every step of quicksort and thus produce a sorting algorithm withO(n logn) running time. Practical implementations of this variant are considerably slower on average, but they are of theoretical interest because they show an optimal selection algorithm can yield an optimal sorting algorithm.
Instead of partitioning into two subarrays using a single pivot, multi-pivot quicksort (also multiquicksort[21]) partitions its input into somes number of subarrays usings − 1 pivots. While the dual-pivot case (s = 3) was considered by Sedgewick and others already in the mid-1970s, the resulting algorithms were not faster in practice than the "classical" quicksort.[33] A 1999 assessment of a multiquicksort with a variable number of pivots, tuned to make efficient use of processor caches, found it to increase the instruction count by some 20%, but simulation results suggested that it would be more efficient on very large inputs.[21] A version of dual-pivot quicksort developed by Yaroslavskiy in 2009[34] turned out to be fast enough[35] to warrant implementation inJava 7, as the standard algorithm to sort arrays ofprimitives (sorting arrays ofobjects is done usingTimsort).[36] The performance benefit of this algorithm was subsequently found to be mostly related to cache performance,[37] and experimental results indicate that the three-pivot variant may perform even better on modern machines.[38][39]
For disk files, an external sort based on partitioning similar to quicksort is possible. It is slower than external merge sort, but doesn't require extra disk space. 4 buffers are used, 2 for input, 2 for output. Let number of records in the file, the number of records per buffer, and the number of buffer segments in the file. Data is read (and written) from both ends of the file inwards. Let represent the segments that start at the beginning of the file and represent segments that start at the end of the file. Data is read into the and read buffers. A pivot record is chosen and the records in the and buffers other than the pivot record are copied to the write buffer in ascending order and write buffer in descending order based comparison with the pivot record. Once either or buffer is filled, it is written to the file and the next or buffer is read from the file. The process continues until all segments are read and one write buffer remains. If that buffer is an write buffer, the pivot record is appended to it and the buffer written. If that buffer is a write buffer, the pivot record is prepended to the buffer and the buffer written. This constitutes one partition step of the file, and the file is now composed of two subfiles. The start and end positions of each subfile are pushed/popped to a stand-alone stack or the main stack via recursion. To limit stack space to, the smaller subfile is processed first. For a stand-alone stack, push the larger subfile parameters onto the stack, iterate on the smaller subfile. For recursion, recurse on the smaller subfile first, then iterate to handle the larger subfile. Once a sub-file is less than or equal to 4 B records, the subfile is sorted in-place via quicksort and written. That subfile is now sorted and in place in the file. The process is continued until all sub-files are sorted and in place. The average number of passes on the file is approximately, but worst case pattern is passes (equivalent to for worst case internal sort).[40]
This algorithm is a combination ofradix sort and quicksort. Pick an element from the array (the pivot) and consider the first character (key) of the string (multikey). Partition the remaining elements into three sets: those whose corresponding character is less than, equal to, and greater than the pivot's character. Recursively sort the "less than" and "greater than" partitions on the same character. Recursively sort the "equal to" partition by the next character (key). Given we sort using bytes or words of lengthW bits, the best case isO(KN) and the worst caseO(2KN) or at leastO(N2) as for standard quicksort, given for unique keysN<2K, andK is a hidden constant in all standardcomparison sort algorithms including quicksort. This is a kind of three-way quicksort in which the middle partition represents a (trivially) sorted subarray of elements that areexactly equal to the pivot.
Also developed by Powers as anO(K) parallelPRAM algorithm. This is again a combination ofradix sort and quicksort but the quicksort left/right partition decision is made on successive bits of the key, and is thusO(KN) forNK-bit keys. Allcomparison sort algorithms implicitly assume thetransdichotomous model withK inΘ(logN), as ifK is smaller we can sort inO(N) time using a hash table orinteger sorting. IfK ≫ logN but elements are unique withinO(logN) bits, the remaining bits will not be looked at by either quicksort or quick radix sort. Failing that, all comparison sorting algorithms will also have the same overhead of looking throughO(K) relatively useless bits but quick radix sort will avoid the worst caseO(N2) behaviours of standard quicksort and radix quicksort, and will be faster even in the best case of those comparison algorithms under these conditions ofuniqueprefix(K) ≫ logN. See Powers[41] for further discussion of the hidden overheads in comparison, radix and parallel sorting.
In any comparison-based sorting algorithm, minimizing the number of comparisons requires maximizing the amount of information gained from each comparison, meaning that the comparison results are unpredictable. This causes frequentbranch mispredictions, limiting performance.[42] BlockQuicksort[43] rearranges the computations of quicksort to convert unpredictable branches todata dependencies. When partitioning, the input is divided into moderate-sizedblocks (which fit easily into thedata cache), and two arrays are filled with the positions of elements to swap. (To avoid conditional branches, the position is unconditionally stored at the end of the array, and the index of the end is incremented if a swap is needed.) A second pass exchanges the elements at the positions indicated in the arrays. Both loops have only one conditional branch, a test for termination, which is usually taken.
The BlockQuicksort technique is incorporated intoLLVM's C++ STL implementation, libcxx, providing a 50% improvement on random integer sequences. Pattern-defeating quicksort (pdqsort), a version of introsort, also incorporates this technique.[32]
Several variants of quicksort exist that separate thek smallest or largest elements from the rest of the input.
Richard Cole and David C. Kandathil, in 2004, discovered a one-parameter family of sorting algorithms, called partition sorts, which on average (with all input orderings equally likely) perform at most comparisons (close to the information theoretic lower bound) and operations; at worst they perform comparisons (and also operations); these are in-place, requiring only additional space. Practical efficiency and smaller variance in performance were demonstrated against optimized quicksorts (ofSedgewick andBentley-McIlroy).[44]
Although saving small subarrays until the end makes sense from an instruction count perspective, it is exactly the wrong thing to do from a cache performance perspective.
on small instances Heapsort is already considerably slower than Quicksort (in our experiments more than 30% forn = 210) and on larger instances it suffers from its poor cache behavior (in our experiments more than eight times slower than Quicksort for sorting 228 elements).
