Quicksort asymptotics

DOI10.1016/S0196-6774(02)00216-XMaRDI QIDQ4799520zbMATH OpenFDO

Authors James Allen Fill, Svante Janson

Publication date 23 March 2003

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0105248

zbMATH Keywords

asymptoticslimit distributiondensityrate of convergencecouplingmoment generating functionnumerical analysisQuicksortsorting algorithmKolmogorov-Smirnov distance\(d_2\)-metric

Mathematics Subject Classification ID

Searching and sorting (68P10) General topics in the theory of algorithms (68W01)

Abstract: The number of comparisons X_n used by Quicksort to sort an array of n distinct numbers has mean mu_n of order n log n and standard deviation of order n. Using different methods, Regnier and Roesler each showed that the normalized variate Y_n := (X_n - mu_n) / n converges in distribution, say to Y; the distribution of Y can be characterized as the unique fixed point with zero mean of a certain distributional transformation. We provide the first rates of convergence for the distribution of Y_n to that of Y, using various metrics. In particular, we establish the bound 2 n^{- 1 / 2} in the d_2-metric, and the rate O(n^{epsilon - (1 / 2)}) for Kolmogorov-Smirnov distance, for any positive epsilon.

Recommendations

• A note on the Quicksort asymptotics
• Refined quicksort asymptotics
• Asymptotic analysis of an optimized quicksort algorithm.
• Rates of convergence for Quicksort
• Large Deviations for Quicksort
• Quicksort revisited
• A limit theorem for “quicksort”
• Approximating the limiting quicksort distribution

Cited in

(28)

• Rates of convergence for Quicksort
• The Number of Symbol Comparisons in QuickSort and QuickSelect
• A note on the Quicksort asymptotics
• The total path length of split trees
• Second phase changes in random \(m\)-ary search trees and generalized quicksort: Convergence rates
• Non-asymptotic distributional bounds for the Dickman approximation of the running time of the Quickselect algorithm
• scientific article; zbMATH DE number 5568413 (Why is no real title available?)
• scientific article; zbMATH DE number 7359768 (Why is no real title available?)
• Random records and cuttings in binary search trees
• Exact \(L^2\)-distance from the limit for QuickSort key comparisons (extended abstract).
• Distributional convergence for the number of symbol comparisons used by QuickSort
• Quicksort: Combining Concurrency, Recursion, and Mutable Data Structures
• An efficient algorithm for overcomplete sparsifying transform learning with signal denoising
• A weakly 1-stable distribution for the number of random records and cuttings in split trees
• Upper tail analysis of bucket sort and random tries
• Upper tail analysis of bucket sort and random tries
• On martingale tail sums for the path length in random trees
• Asymptotic analysis of an optimized quicksort algorithm.
• Smoothed Analysis of Binary Search Trees and Quicksort under Additive Noise
• Density functions for \texttt{QuickQuant} and \texttt{QuickVal}
• Approximating the limiting quicksort distribution
• Approximating perpetuities
• Refined quicksort asymptotics
• Computing and Combinatorics
• Almost sure convergence to the quicksort process
• QuickSort: improved right-tail asymptotics for the limiting distribution, and large deviations
• scientific article; zbMATH DE number 742989 (Why is no real title available?)
• How Many Comparisons Does Quicksort Use?

This page was built for publication: Quicksort asymptotics

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4799520)