Analysis of the expected number of bit comparisons required by quickselect
From MaRDI portal
Publication:1957651
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
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
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