Quicksort: Difference between revisions

Revision as of 03:38, 14 November 2024

Latest revision as of 13:13, 11 July 2025

(26 intermediate revisions by 19 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 '"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 called '''partition-exchange sort'''.<ref>C.L. Foster, ''Algorithms, Abstraction and Implementation'', 1992, {{isbn|0122626605}}, p. 98</ref> The sub-arrays are then sorted [[recursion (computer science)|recursively]]. This can be done [[in-place algorithm|in-place]], requiring small additional amounts of [[Main memory|memory]] to perform the sorting.

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 [[JuanTony SebastianHoare]] 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, thatwhich enabled him to publish an improved version of the algorithm in ALGOL in ''[[Communications of the ACM|Communications of the Association for Computing Machinery]]'', the premier computer science journal of the time.<ref name=alg64 /><ref>{{Cite web |url = http://anothercasualcoder.blogspot.com/2015/03/my-quickshort-interview-with-sir-tony.html |title = My Quickshort interview with Sir Tony Hoare, the inventor of Quicksort |date = 2015-03-15 |publisher = Marcelo M De Barros }}</ref> The ALGOL code is published in [https://dl.acm.org/doi/pdf/10.1145/366622.366642 Communications 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, 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]].

Line 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 - 1)}} and {{mono|(p..hi)}}. Which of the two options we choose depends on which index ('''i''' or '''j''') we return in the partition function when the indices cross, and how we choose our pivot in the partition function ('''floor''' v.s. '''ceiling''').

Let's firstFirst examine the choice of recursing on {{mono|(lo..p)}} and {{mono|(p+1..hi)}}, with the example of sorting an array where multiple identical elements exist '''{{Mono|[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 {{mono|(lo..p)}}would be on (0, 1), which corresponds to the exact same array '''{{Mono|[0, 0]}}'''. A non-advancing separation that causes infinite recursion is produced. It is therefore obvious that '''when recursing on {{mono|(lo..p)}} and {{mono|(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 '''{{Mono|[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 '''{{mono|(lo..p)}}''' causing infinite recursion). It is for the exact same reason why choice of the last element as pivot must be avoided.

The choice of recursing on {{mono|(lo..p - 1)}} and {{mono|(p..hi)}} follows the exact 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 ('''{{Mono|[0, 0]}}'''), and an already sorted array '''{{Mono|[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.

=== Implementation issues ===

Line 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||AnalysisAverage-case of randomized quicksortanalysis}}) with random pivot selection is {{math|1.386 ''n'' log ''n''}}. Median-of-three pivoting brings this down to {{math|[[Binomial coefficient|''C'']]_{''n'', 2} ≈ 1.188 ''n'' log ''n''}}, at the expense of a three-percent increase in the expected number of swaps.{{r|engineering}} An even stronger pivoting rule, for larger arrays, is to pick the [[ninther]], a recursive median-of-three (Mo3), defined as{{r|engineering}}

:{{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 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, weit can maketakes {{math|''n'' − 1}} nested calls before weto reach a list of size 1. This means that the [[Call stack|call tree]] is a linear chain of {{math|''n'' − 1}} nested calls. The {{mvar|i}}th call does {{math|''O''(''n'' − ''i'')}} work to do the partition, and <math>\textstyle\sum_{i=0}^n (n-i) = O(n^2)</math>, so in that case quicksort takes {{math|''O''(''n''²)}} time.

=== Best-case analysis ===

In the most balanced case, each time we perform a partition we dividedivides the list into two nearly equal pieces. This means each recursive call processes a list of half the size. Consequently, we can make only {{math|log₂ ''n''}} nested calls beforecan webe made before reachreaching a list of size 1. This means that the depth of the [[Call stack|call tree]] is {{math|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 {{math|''O''(''n'')}} time all together (each call has some constant overhead, but since there are only {{math|''O''(''n'')}} calls at each level, this is subsumed in the {{math|''O''(''n'')}} factor). The result is that the algorithm uses only {{math|''O''(''n'' log ''n'')}} time.

=== 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).

We list here threeThree common proofs to this claim use percentiles, recurrences, and binary search trees, each providing different insights into quicksort's workings.

==== 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. IfConsistently we could consistently choosechoosing such pivots, we would only have to split the list at most <math>\log_{4/3} n</math> times before reaching lists of size 1, yielding an {{math|''O''(''n'' log ''n'')}} algorithm.

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 startstarting from a random permutation, in each recursive call the's pivot has a random rank in its list, and so ittherefore is in the middle 50 percent aboutapproximately 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—ifhalf weas hitlong as it anyis constanta fractionconsistent amount of the times, that is enough for the desired complexity.

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 278 ⟶ 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>.

WeSimplified endas with athe short calculation:

: <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 294 ⟶ 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'')²)}} 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 376 ⟶ 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 optimisedoptimized quicksorts (of [[Robert Sedgewick (computer scientist)|Sedgewick]] and [[Jon Bentley (computer scientist)|Bentley]]-[[Douglas McIlroy|McIlroy]]).<ref>Richard Cole, David C. Kandathil: [http://www.cs.nyu.edu/cole/papers/part-sort.pdf "The average case analysis of Partition sorts"], European Symposium on Algorithms, 14–17 September 2004, Bergen, Norway. Published: ''Lecture Notes in Computer Science'' 3221, Springer Verlag, pp. 240–251.</ref>

== See also ==

Line 394 ⟶ 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.&nbsp;145–164.

* [[{{cite web |last1=Moller |first1=Faron |author-link1 =Faron Moller]]. [|title=Analysis of Quicksort |url=http://www.cs.swan.ac.uk/~csfm/Courses/CS_332/quicksort.pdf Analysis|access-date=3 ofDecember Quicksort]2024 |archive-url=https://web.archive.org/web/20220707055712/http://www.cs.swan.ac.uk/~csfm/Courses/CS_332/quicksort.pdf |archive-date=7 July 2022}} (CS 332: Designing Algorithms. Department of Computer Science, [[Swansea University]].)

* {{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 }}