Distributional Convergence for the Number of Symbol Comparisons Used by Quickselect

DOI10.1239/aap/1370870125>zbMath1278.68354>arXiv1202.2599>OpenAlexW3104914883>MaRDI QIDQ2837754>

James Allen Fill, Takéhiko Nakama

Publication date: 11 July 2013

Published in: Advances in Applied Probability (Search for Journal in Brave)

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

zbMATH Keywords

limit distributionalmost-sure convergenceprobabilistic sourceL\(^p\)-convergenceQuickQuantQuickSelectQuickValsymbol comparison

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Searching and sorting (68P10) (L^p)-limit theorems (60F25)

Related Items (6)

Towards a realistic analysis of the QuickSelect algorithm ⋮ QuickSelect Tree Process Convergence, With an Application to Distributional Convergence for the Number of Symbol Comparisons Used by Worst-Case Find ⋮ Density functions for \texttt{QuickQuant} and \texttt{QuickVal} ⋮ Towards a Realistic Analysis of Some Popular Sorting Algorithms ⋮ Distributional convergence for the number of symbol comparisons used by QuickSort ⋮ Process convergence for the complexity of radix selection on Markov sources

Uses Software

• Find

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The number of bit comparisons used by quicksort: an average-case analysis
• Multiple Quickselect -- Hoare's Find algorithm for several elements
• Exponential bounds for the running time of a selection algorithm
• Probabilistic analysis of multiple quick select
• The contraction method for recursive algorithms
• Dynamical sources in information theory: A general analysis of trie structures
• Average-case analysis of multiple Quickselect: An algorithm for finding order statistics
• Distributional convergence for the number of symbol comparisons used by QuickSort
• Analysis of the expected number of bit comparisons required by quickselect
• Quickselect and the Dickman Function
• The Number of Symbol Comparisons in QuickSort and QuickSelect
• A limiting distribution for quicksort
• The moments of FIND
• Hoare's Selection Algorithm: A Markov Chain Approach
• Analysis of quickselect : an algorithm for order statistics
• Asymptotic distribution theory for Hoare's selection algorithm
• A limit theorem for “quicksort”
• On the probabilistic worst-case time of ``find

This page was built for publication: Distributional Convergence for the Number of Symbol Comparisons Used by Quickselect