Content deleted Content added
Added 3-way (Dutch national flag) partition quicksort pseudocode. |
Correcting description of the 3-way partition pseudocode accordingly. |
||
Line 196:
'''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 other item of the partition is equal to
The best case for the algorithm now occurs when all elements are equal (or are chosen from a small set of {{math|''k'' ≪ ''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 the <code>partition</code> subroutine takes no longer than linear time).
| |||