Distributional Convergence for the Number of Symbol Comparisons Used by Quickselect

DOI10.1239/aap/1370870125zbMath1278.68354arXiv1202.2599OpenAlexW3104914883MaRDI 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

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