Quicksort is an efficient, general-purpose sorting algorithm. Quicksort was developed by British computer scientist Tony Hoare in 1959 (14 minutes 50 seconds into the programme, interview with Bill Roscoe.) and published in 1961. It is still a commonly used algorithm for sorting. Overall, it is slightly faster than merge sort and heapsort for randomized data, particularly on larger distributions.
Quicksort is a divide-and-conquer algorithm. It works by selecting a "pivot" element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. For this reason, it is sometimes called partition-exchange sort.C.L. Foster, Algorithms, Abstraction and Implementation, 1992, , p. 98 The sub-arrays are then sorted recursively. This can be done in-place, requiring small additional amounts of memory to perform the sorting.
Quicksort is a comparison sort, meaning that it can sort items of any type for which a "less-than" relation (formally, a total order) is defined. It is a comparison-based sort since elements a and b are only swapped in case their relative order has been obtained in the transitive closure of prior comparison-outcomes. Most implementations of quicksort are not stable, meaning that the relative order of equal sort items is not preserved.
Mathematical analysis of quicksort shows that, on average, the algorithm takes comparisons to sort n items. In the worst case, it makes comparisons.
History The quicksort algorithm was developed in 1959 by Tony Hoare while he was a visiting student at Moscow State University. At that time, Hoare was working on a machine translation project for the National Physical Laboratory. As a part of the translation process, he needed to sort the words in Russian sentences before looking them up in a Russian-English dictionary, which was in alphabetical order on magnetic tape. After recognizing that his first idea, insertion sort, would be slow, he came up with a new idea. He wrote the partition part in Mercury Autocode but had trouble dealing with the list of unsorted segments. On return to England, he was asked to write code for Shellsort. Hoare mentioned to his boss that he knew of a faster algorithm, and his boss bet a sixpence that he did not. His boss ultimately accepted that he had lost the bet. Hoare published a paper about his algorithm, including a theoretical analysis, in The Computer Journal Volume 5, Issue 1, 1962, Pages 10–16. Later, Hoare learned about ALGOL and its ability to do recursion, which enabled him to publish an improved version of the algorithm in ALGOL in Communications of the Association for Computing Machinery, the premier computer science journal of the time. The ALGOL code is published in Communications of the ACM (CACM), Volume 4, Issue 7 July 1961, pp 321 Algorithm 63: partition and Algorithm 64: Quicksort.
Quicksort gained widespread adoption, appearing, for example, in Unix as the default library sort subroutine. Hence, it lent its name to the C standard library subroutine and in the reference implementation of Java.
Robert Sedgewick's PhD thesis in 1975 is considered a milestone in the study of Quicksort where he resolved many open problems related to the analysis of various pivot selection schemes including Samplesort, adaptive partitioning by Van Emden as well as derivation of expected number of comparisons and swaps. Jon Bentley and Doug McIlroy in 1993 incorporated various improvements for use in programming libraries, including a technique to deal with equal elements and a pivot scheme known as pseudomedian of nine, where a sample of nine elements is divided into groups of three and then the median of the three medians from three groups is chosen. Bentley described another simpler and compact partitioning scheme in his book Programming Pearls that he attributed to Nico Lomuto. Later Bentley wrote that he used Hoare's version for years but never really understood it but Lomuto's version was simple enough to prove correct. Bentley described Quicksort as the "most beautiful code I had ever written" in the same essay. Lomuto's partition scheme was also popularized by the textbook Introduction to Algorithms although it is inferior to Hoare's scheme because it does three times more swaps on average and degrades to runtime when all elements are equal. McIlroy would further produce an AntiQuicksort () function in 1998, which consistently drives even his 1993 variant of Quicksort into quadratic behavior by producing adversarial data on-the-fly.
Algorithm
Quicksort is a type of divide-and-conquer algorithm for sorting an array, based on a partitioning routine; the details of this partitioning can vary somewhat, so that quicksort is really a family of closely related algorithms. Applied to a range of at least two elements, partitioning produces a division into two consecutive non-empty sub-ranges, in such a way that no element of the first sub-range is greater than any element of the second sub-range. After applying this partition, quicksort then recursively sorts the sub-ranges, possibly after excluding from them an element at the point of division that is at this point known to be already in its final location. Due to its recursive nature, quicksort (like the partition routine) has to be formulated so as to be callable for a range within a larger array, even if the ultimate goal is to sort a complete array. The steps for in-place quicksort are: If the range has fewer than two elements, return immediately as there is nothing to do. (Optional) If the range is very short, use a special-purpose sorting method, and return. For example, ranges of two elements can be sorted with a single comparison. Otherwise select a value, called a pivot, which occurs in the range. (The way the pivot is chosen greatly affects performance, but not correctness.) Partition the range: reorder its elements into sub-ranges, so that all elements with values less than the pivot are in the first sub-range, while all elements with values greater than the pivot are in the second. Elements with values equal to the pivot may be placed in either sub-range, or in a third sub-range between the other two. This middle sub-range is optional, but quicksort requires that the first two sub-ranges are each strictly smaller than the original range, which is most easily achieved by placing at least one pivot element in the middle. Recursively apply quicksort to the two sub-ranges, excluding the middle sub-range which is already in its final position.
These are the basic requirement for correct operation. Details not specified above, including the partition algorithm, and particularly the pivot selection, can greatly affect the algorithm's performance for some input arrays. To discuss the efficiency of quicksort, it is therefore necessary to specify these choices first. Here, we mention two specific partition methods.
Lomuto partition scheme This scheme is attributed to Nico Lomuto and popularized by Bentley in his book Programming Pearls and Cormen et al. in their book Introduction to Algorithms. In most formulations, this scheme chooses as the pivot the last element in the array. The algorithm maintains index as it scans the array using another index such that the elements at through (inclusive) are less than the pivot, and the elements at through (inclusive) are equal to or greater than the pivot. As this scheme is more compact and easier to understand, it is frequently used in introductory material, although it is less efficient than Hoare's original scheme, e.g., when all elements are equal. The complexity of Quicksort with this scheme degrades to when the array is already in order, due to the partition being the worst possible one. There have been various variants proposed to boost performance, including various ways to select the pivot, deal with equal elements, use other sorting algorithms such as insertion sort for small arrays, and so on. In pseudocode, a quicksort that sorts elements at through (inclusive) of an array can be expressed as:
// Sorts (a portion of) an array, divides it into partitions, then sorts those algorithm quicksort(A, lo, hi) is // Ensure indices are in correct order if lo >= hi || lo < 0 then return
// Partition array and get the pivot index p := partition(A, lo, hi)
// Sort the two partitions quicksort(A, lo, p - 1) // Left side of pivot quicksort(A, p + 1, hi) // Right side of pivot
// Divides array into two partitions algorithm partition(A, lo, hi) is pivot := A[hi] // Choose the last element as the pivot
// Temporary pivot index i := lo
for j := lo to hi - 1 do // If the current element is less than or equal to the pivot if A[j] <= pivot then // Swap the current element with the element at the temporary pivot index swap A[i] with A[j] // Move the temporary pivot index forward i := i + 1
// Swap the pivot with the last element swap A[i] with A[hi] return i // the pivot index
Sorting the entire array is accomplished by .
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 pivot at the first pointer, and one less than the pivot 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. 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.