Analysis of the expected number of bit comparisons required by quickselect

DOI10.1007/s00453-009-9294-3zbMath1202.68128arXiv0706.2437OpenAlexW2235490217MaRDI QIDQ1957651

Takéhiko Nakama, James Allen Fill

Publication date: 27 September 2010

Published in: Algorithmica, 2008 Proceedings of the Fifth Workshop on Analytic Algorithmics and Combinatorics (ANALCO) (Search for Journal in Brave)

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

zbMATH Keywords

AsymptoticsQuickselectAverage-case analysisBit comparisonsFindKey comparisonsSearching algorithms

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Searching and sorting (68P10)

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 ⋮ Distributional convergence for the number of symbol comparisons used by QuickSort ⋮ Process convergence for the complexity of radix selection on Markov sources ⋮ Non-asymptotic distributional bounds for the Dickman approximation of the running time of the Quickselect algorithm ⋮ Analysis of swaps in radix selection ⋮ Distributional Convergence for the Number of Symbol Comparisons Used by Quickselect ⋮ Analysis of quickselect under Yaroslavskiy's dual-pivoting algorithm

Uses Software

• Find

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Multiple Quickselect -- Hoare's Find algorithm for several elements
• Mellin transforms and asymptotics: Finite differences and Rice's integrals
• Probabilistic analysis of multiple quick select
• Mellin transforms and asymptotics: Digital sums
• Average-case analysis of multiple Quickselect: An algorithm for finding order statistics
• Quickselect and the Dickman Function
• On a Constant Arising in the Analysis of Bit Comparisons in Quickselect
• The Number of Symbol Comparisons in QuickSort and QuickSelect
• A limiting distribution for quicksort
• Quicksort asymptotics
• Rates of convergence for Quicksort
• 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