Distributional convergence for the number of symbol comparisons used by QuickSort

DOI10.1214/12-AAP866zbMath1272.68482arXiv1202.2601OpenAlexW3194489645MaRDI QIDQ1950265

James Allen Fill

Publication date: 10 May 2013

Published in: The Annals of Applied Probability (Search for Journal in Brave)

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

zbMATH Keywords

limit distributiontameness\(L^{p}\)-convergencekey comparisonsQuickSortde-poissonizationnatural couplingprobabilistic sourcesymbol comparisons

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Searching and sorting (68P10) Zero-one laws (60F20)

Related Items (5)

QuickSelect Tree Process Convergence, With an Application to Distributional Convergence for the Number of Symbol Comparisons Used by Worst-Case Find ⋮ Towards a Realistic Analysis of Some Popular Sorting Algorithms ⋮ Dependence and phase changes in random m‐ary search trees ⋮ Distributional Convergence for the Number of Symbol Comparisons Used by Quickselect ⋮ Analysis of quickselect under Yaroslavskiy's dual-pivoting algorithm

Uses Software

• Quicksort
• Find

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The number of bit comparisons used by quicksort: an average-case analysis
• A characterization of the set of fixed points of the quicksort transformation
• The contraction method for recursive algorithms
• Dynamical sources in information theory: A general analysis of trie structures
• Analysis of the expected number of bit comparisons required by quickselect
• On the subspaces of \(L^p\) \((p > 2)\) spanned by sequences of independent random variables
• Distributional Convergence for the Number of Symbol Comparisons Used by Quickselect
• The limiting distribution for the number of symbol comparisons used by QuickSort is nondegenerate (extended abstract)
• The Number of Symbol Comparisons in QuickSort and QuickSelect
• A limiting distribution for quicksort
• Foundations of Modern Probability
• Probability: A Graduate Course
• Quicksort asymptotics
• Rates of convergence for Quicksort
• A limit theorem for “quicksort”
• Quicksort

This page was built for publication: Distributional convergence for the number of symbol comparisons used by QuickSort