Content deleted Content added
Corrected the initial Hoare's partition pivot value. |
Added 3-way (Dutch national flag) partition quicksort pseudocode. |
||
Line 156:
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 takes [[quadratic 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 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 (portion of an) array, divides it into partitions, then sorts those''
'''algorithm''' quicksort(A, lo, hi) '''is'''
lt,
▲ quicksort(A, right + 1, hi)
''// Divides array into three partitions''
'''algorithm''' 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 pivot''
'''while''' eq <= gt '''do'''
'''if''' A[eq] < pivot '''then'''
''// Swap the elements at the equal and lesser indices''
'''swap''' A[eq] '''with''' A[lt]
''// Increase lesser index''
lt := lt + 1
''// Increase equal index''
eq := eq + 1
'''else''' '''if''' A[eq] > pivot '''then'''
''// Swap the elements at the equal and greater indices''
'''swap''' A[eq] '''with''' A[gt]
''// Decrease greater index''
gt := gt - 1
'''else''' ''// '''if''' A[eq] = pivot '''then'''''
''// Increase equal index''
eq := eq + 1
''// Return lesser and greater indices''
'''return''' lt, gt
The <code>partition</code> algorithm returns indices to the first ('leftmost') and to the last ('rightmost') item of the middle partition. Every item of the partition is equal to <code>p</code> and is therefore sorted. Consequently, the items of the partition need not be included in the recursive calls to <code>quicksort</code>.
| |||