Animated visualization of the quicksort algorithm. The horizontal lines are pivot values.
Class
Sorting algorithm
Worst-case performance
Best-case performance
(simple partition) or (three-way partition and equal keys)
Average performance
Worst-case space complexity
auxiliary (naive) auxiliary (Hoare 1962)
Optimal
No
Preview warning: Page using Template:Infobox algorithm with unknown parameter "stability"
Quicksort is an efficient, general-purpose sorting algorithm. Quicksort was developed by British computer scientist Tony Hoare in 1959[1] and published in 1961.[2] 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.[3]
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.[4] 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.
^"Sir Antony Hoare". Computer History Museum. Archived from the original on 3 April 2015. Retrieved 22 April 2015.
^Hoare, C. A. R. (1961). "Algorithm 64: Quicksort". Comm. ACM. 4 (7): 321. doi:10.1145/366622.366644.
^Skiena, Steven S. (2008). The Algorithm Design Manual. Springer. p. 129. ISBN 978-1-84800-069-8.
^C.L. Foster, Algorithms, Abstraction and Implementation, 1992, ISBN 0122626605, p. 98
Quicksort is an efficient, general-purpose sorting algorithm. Quicksort was developed by British computer scientist Tony Hoare in 1959 and published in...
the related quicksort sorting algorithm, it was developed by Tony Hoare, and thus is also known as Hoare's selection algorithm. Like quicksort, it is efficient...
performance and (asymptotically) optimal worst-case performance. It begins with quicksort, it switches to heapsort when the recursion depth exceeds a level based...
exchange, selection, merging, etc. Exchange sorts include bubble sort and quicksort. Selection sorts include cycle sort and heapsort. Whether the algorithm...
time, using 256 buckets. With some optimizations, it is twice as fast as quicksort for large sets of strings. The name American flag sort comes by analogy...
well-implemented quicksort, it has the advantages of very simple implementation and a more favorable worst-case O(n log n) runtime. Most real-world quicksort variants...
sort, but it is equivalent to quicksort as both recursively partition the elements based on a pivot, and since quicksort is in-place and has lower overhead...
used primarily as an educational tool. More efficient algorithms such as quicksort, timsort, or merge sort are used by the sorting libraries built into popular...
implementation) quickSort :: Ord a => [a] -> [a] -- Using list comprehensions quickSort [] = [] -- The empty list is already sorted quickSort (x:xs) = quickSort [a...
partial_quicksort(A, i, j, k) is if i < j then p ← pivot(A, i, j) p ← partition(A, i, j, p) partial_quicksort(A, i, p-1, k) if p < k-1 then partial_quicksort(A...
interest for designing sorting algorithms; in particular, variants of the quicksort algorithm that must be robust to repeated elements may use a three-way...
Execute Quicksort on A[1 to i-1] and A[i+1 to n]. Combine the responses in order to obtain a sorted array.""" A simple example is randomized quicksort, where...
the expected running time is finite (Las Vegas algorithms, for example Quicksort), and algorithms which have a chance of producing an incorrect result...
much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. However, insertion sort provides several advantages:...
algorithm: these are analogous refinements of the basic quickselect and quicksort algorithms, in that they both start with the quick algorithm, which has...
than quicksort does in its average case, and in terms of moves, merge sort's worst case complexity is O(n log n) - the same complexity as quicksort's best...
distinction in computer science, in 1980. Hoare developed the sorting algorithm quicksort in 1959–1960. He developed Hoare logic, an axiomatic basis for verifying...
passes becomes the bottleneck. Binary MSD radix sort, also called binary quicksort, can be implemented in-place by splitting the input array into two bins...
such as hash tables, arrays, and binary trees, and algorithms such as quicksort, can be useful for creating software. Computer software has special economic...
of data, and Tony Hoare, programming languages pioneer and inventor of Quicksort. The university is associated with eleven winners of the Nobel Prize in...
Global Information
