|
=== Hoare partition scheme ===
[[File:Quicksort-example.gif|350px|thumb|right|An animated demonstration of Quicksort using Hoare's partition scheme. The red outlines show the positions of the left and right pointers (<codecodeR>i</code> and <code>j</code> respectively), the black outlines show the positions of the sorted elements, and the filled black square shows the value that is being compared to (<code>pivot</code>).]]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 boundpivot 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 | 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; a valid partition is found, with the point of division between the crossed pointers (any entries that might be strictly between the crossed pointers are equal to the pivot and can be excluded from both sub-ranges formed). With this formulation it is possible that one sub-range turns out to be the whole original range, which would prevent the algorithm from advancing. Hoare therefore stipulates that at the end, the sub-range containing the pivot element (which still is at its original position) can be decreased in size by excluding that pivot, after (if necessary) exchanging it with the sub-range element closest to the separation; thus, termination of quicksort is ensured.
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" and "less than" respectively; since the formulation uses {{mono|'''do'''...'''while'''}} rather than {{mono|'''repeat'''...'''until'''}} which is actually reflected by the use of strict comparison operators{{Clarify|date=January 2023}}). While there is no reason to exchange elements equal to the boundpivot, 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.) The risk of producing a non-advancing separation is avoided in a different manner than described by Hoare. Such a separation can only result when no inversions are found, with both pointers advancing to the pivot element at the first iteration (they are then considered to have crossed, and no exchange takes place). The division returned is after the final position of the second pointer, so the case to avoid is where the pivot is the final element of the range and all others are smaller than it. Therefore, the pivot choice must avoid the final element (in Hoare's description it could be any element in the range); this is done here by rounding ''down'' the middle position, using the <kbd>floor</kbd> function.<ref>in many languages this is the standard behavior of integer division</ref> This illustrates that the argument for correctness of an implementation of the Hoare partition scheme can be subtle, and it is easy to get it wrong.
In [[pseudocode]],<ref name=":2"/>
|
