Content deleted Content added
Correcting description of the 3-way partition pseudocode accordingly. |
Baongoc124 (talk | contribs) Added "Therefore" to clarify why the recursion ranges after Hoare partition is different than Lomuto's. |
||
Line 120:
The entire array is sorted by {{mono|quicksort(A, 0, length(A) - 1)}}.
Hoare's scheme is more efficient than Lomuto's partition scheme because it does three times fewer swaps on average. Also, as mentioned, the implementation given creates a balanced partition even when all values are equal.<ref name=":1" />{{self-published inline | date=August 2015}}, which Lomuto's scheme does not. Like Lomuto's partition scheme, Hoare's partitioning also would cause Quicksort to degrade to {{math|''O''(''n''<sup>2</sup>)}} for already sorted input, if the pivot was chosen as the first or the last element. With the middle element as the pivot, however, sorted data results with (almost) no swaps in equally sized partitions leading to best case behavior of Quicksort, i.e. {{math|''O''(''n'' log(''n''))}}. Like others, Hoare's partitioning doesn't produce a stable sort. In this scheme, the pivot's final ___location is not necessarily at the index that is returned, as the pivot and elements equal to the pivot can end up anywhere within the partition after a partition step, and may not be sorted until the base case of a partition with a single element is reached via recursion.
'''Subsequent recursions (expansion on previous paragraph)'''
| |||