Approximating the limiting quicksort distribution
From MaRDI portal
Abstract: The limiting distribution of the normalized number of comparisons used by Quicksort to sort an array of n numbers is known to be the unique fixed point with zero mean of a certain distributional transformation S. We study the convergence to the limiting distribution of the sequence of distributions obtained by iterating the transformation S, beginning with a (nearly) arbitrary starting distribution. We demonstrate geometrically fast convergence for various metrics and discuss some implications for numerical calculations of the limiting Quicksort distribution. Finally, we give companion lower bounds which show that the convergence is not faster than geometric.
Recommendations
Cites work
- A characterization of the set of fixed points of the quicksort transformation
- A limit theorem for “quicksort”
- A limiting distribution for quicksort
- How Many Comparisons Does Quicksort Use?
- scientific article; zbMATH DE number 699709 (Why is no real title available?)
- Inequalities for E k(X, Y) when the marginals are fixed
- Some properties of a limiting distribution in Quicksort
Cited in
(27)- A characterization of the set of fixed points of the quicksort transformation
- Perfect simulation from the quicksort limit distribution
- Exact and approximate limit behaviour of the Yule tree's cophenetic index
- Some properties of a limiting distribution in Quicksort
- Distributional convergence for the number of symbol comparisons used by QuickSort
- Almost sure convergence to the quicksort process
- Convergence of the population dynamics algorithm in the Wasserstein metric
- Asymptotic distributions for random median quicksort
- A numerical study of small parameter behavior of some families of distributions
- On tail bounds for random recursive trees
- Implicit renewal theory and power tails on trees
- Information ranking and power laws on trees
- A limiting distribution for quicksort
- Tail behavior of solutions of linear recursions on trees
- Implicit renewal theorem for trees with general weights
- scientific article; zbMATH DE number 1552325 (Why is no real title available?)
- Maximums on trees
- A note concerning the limit distribution of the quicksort algorithm
- Quicksort asymptotics
- Rates of convergence for Quicksort
- QuickSort: Improved right-tail asymptotics for the limiting distribution, and large deviations (Extended Abstract)
- Convergence rates in the implicit renewal theorem on trees
- Computing and Combinatorics
- A limit theorem for “quicksort”
- Stochastic recursions on directed random graphs
- The total path length of split trees
- On the tails of the limiting Quicksort distribution
This page was built for publication: Approximating the limiting quicksort distribution
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2772925)
