Quicksort: Difference between revisions

This scheme is attributed to Nico Lomuto and popularized by Bentley in his book Programming Pearls<ref name=":3" /> and Corman et al in their book Introduction to Algorithms.<ref name=":2" /> This scheme chooses a pivot which is typically the last element in the array. The algorithm maintains the index to put pivot in variable <code>i</code> and each time when it finds an element less than or equal to pivot, this index is incremented and that element would be placed before the pivot. As pivot is selected from last index and is placed after all equal elements, this scheme produces stable sort. As this scheme is more compact and easy to understand, it is frequently used in introductory material however it is less efficient than Hoare's original scheme.<ref>{{Cite web|url = https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/3463|title = Java 7's Dual Pivot Quicksort|date = 2012|accessdate = |website = |publisher = Technische Universität Kaiserslautern|last = Wild|first = Sebastian}}</ref> This scheme degrade to <math>O(n^2)</math> when array is already sorted as well as when the array has all equal elements.<ref name=":1" /> There have been various variants proposed to boost performance including various ways to select pivot, deal with equal elements, use other sorting algorithms such as Insertion sort for small arrays and so on.

This is the original partition scheme described by C.A.R. Hoare using two indices that moves in opposite direction until an inversion is found in which case the elements are swapped to bring them in relative sort order.<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}}</ref> When the indices crosses each other, algorithm stops and returns the index value. There are many variants of this algorithm, for example, selecting pivot from <code>A[hi]</code> instead of <code>A[lo]</code>. Hoare scheme is more efficient than Lomuto's partition scheme because it does 3 times less swaps on average and it creates efficient partitions even when all values are equal.<ref name=":1" /> Like Lomuto's partition scheme, Hoare partitioning also causes Quicksort to degrade to <math>O(n^2)</math> when array is already sorted.