Live briefing
Everything about Quicksort
Divide and conquer sorting algorithm
Quicksort is an efficient, general-purpose sorting algorithm. Quicksort was developed by British computer scientist Tony Hoare in 1959 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. Wikipedia →
🧭 Start here: a 6-step reading path
- Read the overview: QuicksortA 5-minute orientation
- Skim a recent paper: Vectorized and performance‐portable quicksortInfluential work since 2022
- Pick up a classic book: Introduction to AlgorithmsThe most-reprinted book on the subject
- Read the landmark paper: QuicksortCited 763 times
- Go sideways: QuickselectA closely related topic
- Go sideways: Sorting algorithmA closely related topic
📖 Definitions
Noun A sorting algorithm that operates by recursively partitioning the items to be sorted into two sets.
Verb To sort with such an algorithm.
🗂️ The subject at a glance
🏆 Landmark papers (most cited)
Quicksort
Algorithm 64: Quicksort
Implementing Quicksort programs
A limit theorem for “quicksort”
The analysis of Quicksort programs
A limiting distribution for quicksort
Phase Change of Limit Laws in the Quicksort Recurrence under Varying Toll Functions
Optimal Sampling Strategies in Quicksort and Quickselect
🆕 Influential since 2022
📚 Books worth reading
Introduction to AlgorithmsThomas H. Cormen, Charles E. Leiserson · 1990
Introduction to automata theory, languages, and computationJohn E. Hopcroft, Jeffrey D. Ullman · 1979
An introduction to computer scienceJean-Paul Tremblay, Richard B. Bunt · 1979
Data structures and algorithm analysis in CMark Allen Weiss · 1993
Data structures & algorithm analysis in JavaMark Allen Weiss · 1999
Parallel Programming in C with MPI and OpenMPMichael J. Quinn · 2003
Let Us C++Yashavant Kanetkar · 2002
Data structures and algorithms in JavaAdam Drozdek · 2001
Ranked by number of editions on Open Library, a rough measure of how lasting a book is.
🔗 Related topics
- Quickselect In computer science, quickselect is a selection algorithm to find the kth smallest element in an unordered list, also known as the kth order statistic…
- Sorting algorithm In computer science, a sorting algorithm is an algorithm that puts elements of a list into an order. The most frequently used orders are numerical order…
- Merge sort Merge sort (also commonly spelled as mergesort or merge-sort) is an efficient, general-purpose, comparison-based sorting algorithm. Most implementations…
- Spreadsort Spreadsort is a sorting algorithm invented by Steven J. Ross in 2002. It combines concepts from distribution-based sorts, such as radix sort and bucket…
- Samplesort Samplesort is a sorting algorithm that is a divide and conquer algorithm often used in parallel processing systems. Conventional divide and conquer sorting…
- Heapsort In computer science, heapsort is an efficient, comparison-based sorting algorithm that reorganizes an input array into a heap (a data structure where each…
- Introsort Introsort or introspective sort is a hybrid sorting algorithm that provides both fast average performance and (asymptotically) optimal worst-case performance…
- Proportion extend sort Proportion extend sort (abbreviated as PESort) is an in-place, comparison-based sorting algorithm which attempts to improve on the performance, particularly…