Content deleted Content added
→Algorithm: Rewrote parts, indicating considerable variability within the "quicksort" family, and even within the "Hoare partition scheme" |
m →Hoare partition scheme: spurious semicolon |
||
Line 65:
The original partition scheme described by [[Tony Hoare]] uses two pointers (indices into the range) that start at both ends of the array being partitioned, then move toward each other, until they detect an inversion: a pair of elements, one greater than the bound (Hoare's terms for the pivot value) at the first pointer, and one less than the bound at the second pointer; if at this point the first pointer is still before the second, these elements are in the wrong order relative to each other, and they are then exchanged.<ref>{{Cite journal | title = Quicksort | url = http://comjnl.oxfordjournals.org/content/5/1/10 | journal = The Computer Journal | date = 1962-01-01 | issn = 0010-4620 | pages = 10–16 | volume = 5 | issue = 1 | doi = 10.1093/comjnl/5.1.10 | first = C. A. R. | last = Hoare | author-link = Tony Hoare | doi-access = free }}</ref> After this the pointers are moved inwards, and the search for an inversion is repeated; when eventually the pointers cross (the first points after the second), no exchange is performed; the partition is now complete, and the point of division (between the crossed pointers) is determined.
With respect to this original description, implementations often make minor but important variations. Notably, the scheme as presented below includes elements equal to the pivot among the candidates for an inversion (so "greater than or equal" and "less than or equal" tests are used instead of "greater than" respectively "less than"). While there is no reason to exchange elements equal to the bound, this change allows tests on the pointers themselves to be omitted, which are otherwise needed to ensure they do not run out of range. Indeed, since at least one instance of the pivot value is present in the range, the first advancement of either pointer cannot pass across this instance if an inclusive test is used; once an exchange is performed, these exchanged elements are now both strictly ahead of the pointer that found them, preventing that pointer from running off. (The latter is true independently of the test used, so it would be possible to use the inclusive test only when looking for the first inversion. However using an inclusive test throughout also ensures that a division near the middle is found when all elements in the range are equal, which gives an important efficiency gain for sorting arrays with many equal elements.) There is also a concern of never producing a division at one of the extremities of the given range, as that would prevent the algorithm from advancing, causing non termination; this can only happen the first search already produces a false inversion (crossed pointers). In the version below the division returned is after the returned final value of the second pointer; the worry is than that it could point at the last element of the range, which would happen if that element is chosen as the pivot and all other elements in the range are smaller (both pointers then advance to the final element, and being equal no exchange is done). Therefore the pivot choice must avoid the final element, which is done here by rounding down the middle position, using the <kbd>floor</kbd> function
In [[pseudocode]],<ref name=":2"/>
Line 92:
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 an 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. The next two segments that the main algorithm recurs on are {{mono|(lo..p)}} (elements ≤ pivot) and {{mono|(p+1..hi)}} (elements ≥ pivot) as opposed to {{mono|(lo..p-1)}} and {{mono|(p+1..hi)}} as in Lomuto's scheme.
=== Implementation issues ===
| |||