Content deleted Content added
m →Algorithm: Removed inappropriate article "the" before "quicksort" under the 4th bullet. |
m →Algorithm: Fixed faulty parentheses in pseudocode. |
||
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 84:
In [[pseudocode]],<ref name=":2"/>
''// Sorts (a
'''algorithm''' quicksort(A, lo, hi) '''is'''
'''if''' lo >= 0 && hi >= 0 && lo < hi '''then'''
Line 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'''
| |||