Quicksort is an efficient general purpose sorting algorithm developed in 1959 by Tony Hoare while he was a visiting student at Moscow State University. It works by choosing a pivot element, partitioning the rest into items smaller and larger than the pivot, and sorting the two parts recursively; on average it takes O(n log n) comparisons to sort n items, and for decades it has been the practical sorting workhorse of standard libraries. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/
Facts
Core PrinciplePick a pivot, split everything else into smaller and larger, and sort each side the same way; the recursion does the rest. 1 FAQs
Does quicksort always sort in O(n log n) time?
No, that is the average case; the worst case is O(n^2) comparisons.
No. The O(n log n) figure is the average case. In the worst case, quicksort makes O(n^2) comparisons, which happens when the chosen pivots keep splitting the items very unevenly. Pivot choice therefore matters in practice.
Connections
Associated With
In Field
Invented By
Source Wikipedia: Quicksort
Sources
1. Wikipedia: Quicksort
Wikimedia FoundationIntroduction, History and Formal analysis sections
The quicksort algorithm was developed in 1959 by Tony Hoare while he was a visiting student at Moscow State University.
Formal analysis section
On average, the algorithm takes O(n log n) comparisons to sort n items.
Invented By: Tony Hoare, History section
The quicksort algorithm was developed in 1959 by Tony Hoare while he was a visiting student at Moscow State University.
In Group: Sorting and Searching Algorithms, Lead
Quicksort is an efficient, general-purpose sorting algorithm.
View the Source Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.