Content deleted Content added
m →Parallelization: Added middle initials to correctly distinguish author as per citation (and [[]] red-coding) - there are multiple 'David Powers' active in IT. Spelling/grammar/punctuation/typographical correction |
m Dating maintenance tags: {{Citation needed}} |
||
| (39 intermediate revisions by 28 users not shown) | |||
Line 16:
'''Quicksort''' is an efficient, general-purpose [[sorting algorithm]]. Quicksort was developed by British computer scientist [[Tony Hoare]] in 1959<ref>{{cite web |title=Sir Antony Hoare |publisher=Computer History Museum |access-date=22 April 2015 |url=http://www.computerhistory.org/fellowawards/hall/bios/Antony,Hoare/ |url-status=dead |archive-url=https://web.archive.org/web/20150403184558/http://www.computerhistory.org/fellowawards/hall/bios/Antony%2CHoare/ |archive-date=3 April 2015}}</ref> and published in 1961.<ref name=alg64>{{Cite journal |last1 = Hoare |first1 = C. A. R. |author-link1 = Tony Hoare |title = Algorithm 64: Quicksort |doi = 10.1145/366622.366644 |journal = [[Communications of the ACM|Comm. ACM]] |volume = 4 |issue = 7 |pages = 321 |year = 1961 }}</ref> It is still a commonly used algorithm for sorting. Overall, it is slightly faster than [[merge sort]] and [[heapsort]] for randomized data, particularly on larger distributions.<ref name="skiena">{{cite book |first=Steven S. |last=Skiena |year=2008 |author-link=Steven Skiena |title=The Algorithm Design Manual |url=https://books.google.com/books?id=7XUSn0IKQEgC |publisher=Springer |isbn=978-1-84800-069-8 |page=129}}</ref>
Quicksort is a [[divide-and-conquer algorithm]]. It works by selecting a
Quicksort is a [[comparison sort]], meaning that it can sort items of any type for which a "less-than" relation (formally, a [[total order]]) is defined. It is a comparison-based sort since elements ''a'' and ''b'' are only swapped in case their relative order has been obtained in the transitive closure of prior comparison-outcomes. Most implementations of quicksort are not [[Sorting algorithm#Stability|stable]], meaning that the relative order of equal sort items is not preserved.
Line 23:
== History ==
The quicksort algorithm was developed in 1959 by [[Tony Hoare]] while he was a visiting student at [[Moscow State University]]. At that time, Hoare was working on a [[machine translation]] project for the [[National Physical Laboratory, UK|National 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 on [[magnetic tape data storage|magnetic tape]].<ref>{{Cite journal |last = Shustek |first = L. |title = Interview: An interview with C.A.R. Hoare |doi = 10.1145/1467247.1467261 |journal = [[Communications of the ACM|Comm. ACM]] |volume = 52 |issue = 3 |pages = 38–41 |year = 2009 |s2cid = 1868477 }}</ref> After recognizing that his first idea, [[insertion sort]], would be slow, he came up with a new idea. He wrote the partition part in Mercury [[Autocode]] but had trouble dealing with the list of unsorted segments. On return to England, he was asked to write code for [[Shellsort]]. Hoare mentioned to his boss that he knew of a faster algorithm and his boss bet a [[Sixpence (British coin)|sixpence]] that he did not. His boss ultimately accepted that he had lost the bet. Hoare published a paper about his algorithm in [[The Computer Journal]] [https://academic.oup.com/comjnl/article/5/1/10/395338?login=false Volume 5, Issue 1, 1962, Pages 10–16]. Later, Hoare learned about [[ALGOL]] and its ability to do recursion,
Quicksort gained widespread adoption, appearing, for example, in [[Unix]] as the default library sort subroutine. Hence, it lent its name to the [[C standard library]] subroutine {{mono|[[qsort]]}}<ref name="engineering" /> and in the reference implementation of [[Java (programming language)|Java]].
[[Robert Sedgewick (computer scientist)|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 including [[Samplesort]], adaptive partitioning by Van Emden<ref>{{Cite journal |title=Algorithms 402: Increasing the Efficiency of Quicksort |journal=Commun. ACM |date=1970-11-01 |issn=0001-0782 |pages=693–694 |volume=13 |issue=11 |doi=10.1145/362790.362803 |first=M. H. |last=Van Emden| s2cid=4774719|doi-access=free }}</ref> as well as derivation of expected number of comparisons and swaps.<ref name="engineering" /> [[Jon Bentley (computer scientist)|Jon Bentley]] and [[Douglas McIlroy|Doug McIlroy]] in 1993 incorporated various improvements for use in programming libraries, including a technique to deal with equal elements and a pivot scheme known as ''pseudomedian 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.<ref name="engineering" /> Bentley described another simpler and compact partitioning scheme in his book ''Programming Pearls'' that he attributed to [[Nico 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.<ref>{{Cite book |title=Beautiful Code: Leading Programmers Explain How They Think |editor1-last=Oram |editor1-first=Andy |editor2-last=Wilson |editor2-first=Greg |publisher=O'Reilly Media |year=2007 |isbn=978-0-596-51004-6| pages=30 |chapter=The most beautiful code I never wrote |first=Jon |last=Bentley |author-link=Jon Bentley (computer scientist)}}</ref> 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 textbook ''[[Introduction to Algorithms]]'' although it is inferior to Hoare's scheme because it does three times more swaps on average and degrades to {{math|''O''(''n''<sup>2</sup>)}} runtime when all elements are equal.<ref name=":1">{{Cite web |title=Quicksort Partitioning: Hoare vs. Lomuto |url=https://cs.stackexchange.com/q/11550 |website=cs.stackexchange.com |access-date=2015-08-03}}</ref>{{self-published inline |date=August 2015}} McIlroy would further produce an ''AntiQuicksort'' ({{mono|aqsort}}) function in 1998, which consistently drives even his 1993 variant of Quicksort into quadratic behavior by producing adversarial data on-the-fly.<ref>{{cite journal |last1=McIlroy |first1=M. D. |title=A killer adversary for quicksort |journal=Software: Practice and Experience |volume=29 |pages=341–344 |doi=10.1002/(SICI)1097-024X(19990410)29:4<341::AID-SPE237>3.0.CO;2-R |date=10 April 1999 |issue=4 |s2cid=35935409 |url=https://www.cs.dartmouth.edu/~doug/mdmspe.pdf}}</ref>
== Algorithm ==
Line 35:
# Otherwise pick a value, called a ''pivot'', that occurs in the range (the precise manner of choosing depends on the partition routine, and can involve randomness).
# ''Partition'' the range: reorder its elements, while determining a point of division, so that all elements with values less than the pivot come before the division, while all elements with values greater than the pivot come after it; elements that are equal to the pivot can go either way. Since at least one instance of the pivot is present, most partition routines ensure that the value that ends up at the point of division is equal to the pivot, and is now in its final position (but termination of quicksort does not depend on this, as long as sub-ranges strictly smaller than the original are produced).
# [[Recursion (computer science)|Recursively]] apply
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.
Line 43:
This scheme is attributed to Nico Lomuto and popularized by Bentley in his book ''Programming Pearls''<ref name=":3" /> and Cormen ''et al.'' in their book ''[[Introduction to Algorithms]]''.<ref name=":2"/> In most formulations this scheme chooses as the pivot the last element in the array. The algorithm maintains index {{mono|i}} as it scans the array using another index {{mono|j}} such that the elements at {{mono|lo}} through {{mono|i-1}} (inclusive) are less than the pivot, and the elements at {{mono|i}} through {{mono|j}} (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.<ref>{{Cite thesis |url = https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/3463 |title = Java 7's Dual Pivot Quicksort |date = 2012 |publisher = Technische Universität Kaiserslautern |last = Wild |first = Sebastian}}</ref> The complexity of Quicksort with this scheme degrades to {{math|''O''(''n''<sup>2</sup>)}} when the array is already in order, due to the partition being the worst possible one.<ref name=":1" /> 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 as [[insertion sort]] for small arrays, and so on. In [[pseudocode]], a quicksort that sorts elements at {{mono|lo}} through {{mono|hi}} (inclusive) of an array {{mvar|A}} can be expressed as:<ref name=":2">{{Introduction to Algorithms|3 |chapter=Quicksort |pages=170–190}}</ref>
''// Sorts (a
'''algorithm''' quicksort(A, lo, hi) '''is'''
''// Ensure indices are in correct order''
Line 61:
''// Temporary pivot index''
i := lo
'''for''' j := lo '''to''' hi - 1 '''do'''
''// If the current element is less than or equal to the pivot''
'''if''' A[j] <= pivot '''then'''
''// Move the temporary pivot index forward''▼
i := i + 1▼
''// 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 A[i] '''with''' A[hi]
'''return''' i ''// the pivot index''
Line 79 ⟶ 78:
=== Hoare partition scheme ===
[[File:Quicksort-example.gif|350px|thumb|right|An animated demonstration of Quicksort using Hoare's partition scheme. The red outlines show the positions of the left and right pointers (<code>i</code> and <code>j</code> respectively), the black outlines show the positions of the sorted elements, and the filled black square shows the value that is being compared to (<code>pivot</code>).]]The original partition scheme described by [[Tony 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
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 uses {{mono|'''do'''...'''while'''}} rather than {{mono|'''repeat'''...'''until'''}} which is actually reflected by the use of strict comparison operators{{Clarify|date=January 2023}}). While there is no reason to exchange elements equal to the
In [[pseudocode]],<ref name=":2"/>
''// Sorts (a
'''algorithm''' quicksort(A, lo, hi) '''is'''
'''if''' lo >= 0 && hi >= 0 && lo < hi '''then'''
Line 124 ⟶ 123:
'''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 '''{{Mono|"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 '''{{Mono|[5, 2, 3, 1, 0]}}''', following the scheme, after the first partition the array becomes '''{{Mono|[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 {{mono|(lo..p)}} and {{mono|(p+1..hi)}}, or {{mono|(lo..p
The choice of recursing on {{mono|(lo..p
=== Implementation issues ===
Line 146 ⟶ 145:
It puts a median into <code>A[hi]</code> first, then that new value of <code>A[hi]</code> is used for a pivot, as in a basic algorithm presented above.
Specifically, the expected number of comparisons needed to sort {{mvar|n}} elements (see {{Section link||
:{{math|ninther(''a'') {{=}} median(Mo3(first {{sfrac|1|3}} of ''a''), Mo3(middle {{sfrac|1|3}} of ''a''), Mo3(final {{sfrac|1|3}} of ''a''))}}
Line 158 ⟶ 157:
To solve the Lomuto partition scheme problem (sometimes called the [[Dutch national flag problem]]<ref name="engineering" />), 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 the {{mono|[[qsort]]}} of [[Version 7 Unix]].<ref name="engineering">{{cite journal |first1=Jon L. |last1=Bentley |first2=M. Douglas |last2=McIlroy |title=Engineering a sort function |journal=Software: Practice and Experience |volume=23 |issue=11 |pages=1249–1265 |year=1993 |url=http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.14.8162 |doi=10.1002/spe.4380231105|citeseerx=10.1.1.14.8162 |s2cid=8822797 }}</ref>) 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
'''algorithm''' quicksort(A, lo, hi) '''is'''
'''if''' lo >= 0 && lo < hi '''then'''
Line 217 ⟶ 216:
The most unbalanced partition occurs when one of the sublists returned by the partitioning routine is of size {{math|''n'' − 1}}.<ref name="unbalanced">The other one may either have {{math|1}} element or be empty (have {{math|0}} elements), depending on whether the pivot is included in one of subpartitions, as in the Hoare's partitioning routine, or is excluded from both of them, like in the Lomuto's routine.</ref> 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,
=== Best-case analysis ===
In the most balanced case, each
=== Average-case analysis ===
To sort an array of {{mvar|n}} distinct elements, quicksort takes {{math|''O''(''n'' log ''n'')}} time in expectation, averaged over all {{math|''n''!}} permutations of {{mvar|n}} elements with [[Uniform distribution (discrete)|equal 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 (Cormen ''et al.'', ''[[Introduction to Algorithms]]'',<ref name=":2"/> Section 7.3).
==== Using percentiles ====
If each pivot has rank somewhere in the middle 50 percent, that is, between the 25th [[percentile]] and the 75th percentile, then it splits the elements with at least 25% and at most 75% on each side.
When the input is a random permutation, the pivot has a random rank, and so it is not guaranteed to be in the middle 50 percent. However, when
Using more careful arguments, it is possible to extend this proof, for the version of Quicksort where the pivot is randomnly chosen,
to show a time bound that holds ''with high probability'': specifically, for any give <math>a\ge 4</math>, let <math>c=(a-4)/2</math>, then with probability at least <math>1-\frac{1}{n^c}</math>, the number of comparisons will not exceed <math>2an\log_{4/3}n</math>.<ref>{{cite book |last1=Motwani |first1= Rajeev |last2= Raghavan|first2= Prabhakar |date= |title= Randomized Algorithms|url= |___location= |publisher= Cambridge University Press|page= |isbn=9780521474658 |access-date=}}</ref>
▲When the input is a random permutation, the pivot has a random rank, and so it is not guaranteed to be in the middle 50 percent. However, when we start from a random permutation, in each recursive call the pivot has a random rank in its list, and so it is in the middle 50 percent about half the time. That is good enough. 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 gets {{mvar|k}} heads. Although this could take a long time, on average only {{math|2''k''}} flips are required, and the chance that the coin won't get {{mvar|k}} heads after {{math|100''k''}} flips is highly improbable (this can be made rigorous using [[Chernoff bound]]s). By the same argument, Quicksort's recursion will terminate on average at a call depth of only <math>2 \log_{4/3} n</math>. But if its average call depth is {{math|''O''(log ''n'')}}, and each level of the call tree processes at most {{mvar|n}} elements, the total amount of work done on average is the product, {{math|''O''(''n'' log ''n'')}}. The algorithm does not have to verify that the pivot is in the middle half—if we hit it any constant fraction of the times, that is enough for the desired complexity.
==== Using recurrences ====
Line 264 ⟶ 267:
</math>
Solving the recurrence gives {{math|''C''(''n'') {{=}} 2 ''n'' ln ''n'' ≈ 1.39 ''n'' log<sub>2</sub> ''n''}}.
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. A [[comparison sort]] cannot use less than {{math|log<sub>2</sub>(''n''!)}} comparisons on average to sort {{mvar|n}} items (as [[Comparison sort#Lower bound for the average number of comparisons|explained in the article Comparison sort]]) and in case of large {{mvar|n}}, [[Stirling's approximation]] yields {{math|log<sub>2</sub>(''n''!) ≈ ''n''(log<sub>2</sub> ''n'' − log<sub>2</sub> ''e'')}}, 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.
Line 279 ⟶ 282:
Observe that since <math>(x_1,x_2,\ldots,x_n)</math> is a random permutation, <math>(x_1,x_2,\ldots,x_j,x_i)</math> is also a random permutation, so the probability that <math>x_i</math> is adjacent to <math>x_j</math> is exactly <math>\frac{2}{j+1}</math>.
: <math>\operatorname{E}[C] = \sum_i \sum_{j<i} \frac{2}{j+1} = O\left(\sum_i \log i\right)=O(n \log n).</math>
Line 295 ⟶ 298:
From a bit complexity viewpoint, variables such as ''lo'' and ''hi'' do not use constant space; it takes {{math|''O''(log ''n'')}} bits to index into a list of {{mvar|n}} items. Because there are such variables in every stack frame, quicksort using Sedgewick's trick requires {{math|''O''((log ''n'')<sup>2</sup>)}} bits of space. This space requirement isn't too terrible, though, since if the list contained distinct elements, it would need at least {{math|''O''(''n'' log ''n'')}} bits of space.
Stack-free versions of Quicksort have been proposed. These use <math>O(1)</math> additional space (more precisely, one cell of the type
Another, less common, not-in-place, version of quicksort uses {{math|''O''(''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.▼
of the sorted records, in order to exchange records, and a constant number of integer variables used as indices).<ref>{{cite conference |last= Ďurian|first= Branislav|date= |title=Quicksort without a stack |url= |work= |book-title= Mathematical Foundations of Computer Science 1986: Proceedings of the 12th Symposium |conference=MFCS 1986 |___location= Bratislava, Czechoslovakia|publisher= Springer Berlin Heidelberg|access-date=}}</ref>
▲Another, less common, not-in-place, version of quicksort{{citation needed|date=July 2025}} uses {{math|''O''(''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.
== Relation to other algorithms ==
Line 348 ⟶ 354:
==== External quicksort ====
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
==== Three-way radix quicksort ====
Line 377 ⟶ 383:
=== Generalization ===
[[Richard J. Cole|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 <math>n\log n + {O}(n)</math> comparisons (close to the information theoretic lower bound) and <math>{\Theta}(n\log n)</math> operations; at worst they perform <math>{\Theta}(n\log^2 n)</math> comparisons (and also operations); these are in-place, requiring only additional <math>{O}(\log n)</math> space. Practical efficiency and smaller variance in performance were demonstrated against
== See also ==
Line 395 ⟶ 401:
* [[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.
*
* {{Cite journal | last1 = Martínez | first1 = C. | last2 = Roura | first2 = S. | doi = 10.1137/S0097539700382108 | title = Optimal Sampling Strategies in Quicksort and Quickselect | journal = [[SIAM Journal on Computing|SIAM J. Comput.]] | volume = 31 | issue = 3 | pages = 683–705 | year = 2001 | citeseerx = 10.1.1.17.4954 }}
* {{Cite journal | last1 = Bentley | first1 = J. L. | last2 = McIlroy | first2 = M. D. | doi = 10.1002/spe.4380231105 | title = Engineering a sort function | journal = Software: Practice and Experience | volume = 23 | issue = 11 | pages = 1249–1265 | year = 1993 | citeseerx = 10.1.1.14.8162 | s2cid = 8822797 }}
| |||