Quicksort

By Robert Sedgewick. 1962

. - Let X n be the number of comparisons needed by the sorting algorithm Quicksort to sort a list of n numbers into their natural ordering. We show that (X n — E(X n ))/n converges weakly to some random variable Y. The distribution of Y is characterized as the fixed point of some contraction. It satisfies a recursive équation, which is used to provide recursive relations for the moments. The random variable Y has exponential tails. Therefore the probability that Quicksort performs badly, e. g. that. X n is larger thon 2 E (X n

Subfields: Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Optimization & Training

Citations in the corpus

Measuring the Algorithmic Efficiency of Neural Networks (2020, background): “6 [Hoare, 1962] Hoare, C. A. (1962).”
Randomized algorithms (1995, unknown): “The earliest instance of this phenomenon can be found in the behavior of the Quicksort algorithm [Hoare 1962].”
Classification of time series by shapelet transformation (2013, methodology): “Only the median is required for calculating MM, which can be found in O ( n ) time using Quickselect Hoare (1962).”
A social learning particle swarm optimization algorithm for scalable optimization (2015, background): “which can be attained by various sorting algorithms such as quick sort [31].”
Preference-based Online Learning with Dueling Bandits: A Survey (2018, background): “…between adjacent parameters is stochastically uniform across the ranking, they ﬁrst show that the output of a single call of the QuickSort algorithm (Hoare, 1962) is a good approximation to the ground-truth ranking in terms of the quality of a ranking estimate by its displacement with respect to…”
The Algorithm Design Manual (2020, methodology): “Quicksort was invented by Hoare [Hoa62], with careful analysis and implementation by Sedgewick [Sed78].”