Quicksort: Difference between revisions

Revision as of 05:15, 4 April 2021

Revision as of 08:27, 4 April 2021

Line 63:

=== Hoare partition scheme ===

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; thea valid partition is now completefound, andwith 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 determinedensured.

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"; since the formulation uses {{mono|'''do'''...'''while''' rather than '''repeat'''...'''until'''}} this is actually reflected by the use of strict comparison operators). 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.) ThereThe isrisk alsoof producing a concernnon-advancing ofseparation neveris producingavoided in a divisiondifferent atmanner onethan ofdescribed theby extremitiesHoare. ofSuch thea givenseparation range,can asonly thatresult wouldwhen preventno theinversions algorithmare from advancingfound, causingwith nonboth termination;pointers thisadvancing canto onlythe happenpivot element at the first searchiteration already(they producesare athen falseconsidered inversionto have (crossed, pointers).and Inno theexchange versiontakes belowplace). theThe division returned is after the returned final valueposition of the second pointer;, so the worrycase isto thanavoid thatis itwhere couldthe pointpivot atis the lastfinal element of the range, whichand wouldall happenothers ifare thatsmaller elementthan isit. chosen asTherefore the pivot andchoice allmust other elements inavoid the rangefinal are smallerelement (bothin pointersHoare's thendescription advanceit tocould thebe finalany element, andin beingthe equal no exchange is donerange).; Therefore the pivot choice must avoid the final element, whichthis 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"/>