(algorithm)
Definition: Pick an element from the array (the pivot), partition the remaining elements into those greater than and less than this pivot, and recursively sort the partitions. There are many variants of the basic scheme above: to select the pivot, to partition the array, to stop the recursion or switch to another algorithm for small partitions, etc.
Generalization (I am a kind of ...)
in-place sort, Las Vegas algorithm when the pivot is picked randomly.
Specialization (... is a kind of me.)
balanced quicksort, multikey Quicksort, introspective sort.
Aggregate parent (I am a part of or used in ...)
q sort.
Aggregate child (... is a part of or used in me.)
partition, divide and conquer, recursion, Select, sublinear time algorithm.
See also external quicksort, dual-pivot quicksort.
Note: Quicksort has running time Θ(n²) in the worst case, but it is typically O(n log n). In practical situations, a finely tuned implementation of quicksort beats most sort algorithms, including sort algorithms whose theoretical complexity is O(n log n) in the worst case.
Select can be used to always pick good pivots, thus giving a variant with O(n log n) worst-case running time.
Newer variants, such as dual-pivot quicksort, are faster because they access less memory.
Author: CM
Comparison of quicksort, heapsort, and merge sort on modern processors.
Quicksort sort illustrated followed by a race between Quicksort and bubble sort.
An analysis of bubble sort, insertion sort, and quick sort.
Merge sort vs. quick sort race. First a random permutation, then a near-worst case for merge sort.
Quicksort illustrated through a Hungarian folk dance: Küküllőmenti legényes. Created at Sapientia University.
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 6 April 2023.
HTML page formatted Thu Apr 6 14:40:22 2023.
Cite this as:
Conrado Martinez, "quicksort", in
Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 6 April 2023. (accessed TODAY)
Available from: https://www.nist.gov/dads/HTML/quicksort.html