Towards a realistic analysis of the QuickSelect algorithm
From MaRDI portal
Publication:290901
DOI10.1007/s00224-015-9633-5zbMath1341.68035OpenAlexW1145223112MaRDI QIDQ290901
James Allen Fill, Brigitte Vallée, Thu Hien Nguyen Thi, Julien Clément
Publication date: 3 June 2016
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00224-015-9633-5
permutationsselection probleminformation theoryasymptotic estimatespattern matchingprobabilistic analysis of algorithmsQuickselectRice's methodsorting and searching algorithms
Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)
Related Items
The Depoissonisation quintet: Rice-Poisson-Mellin-Newton-Laplace ⋮ Process convergence for the complexity of radix selection on Markov sources ⋮ Dichotomic Selection on Words: A Probabilistic Analysis
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Mellin transforms and asymptotics: Finite differences and Rice's integrals
- Dynamical sources in information theory: Fundamental intervals and word prefixes
- Dynamical sources in information theory: A general analysis of trie structures
- Analysis of the expected number of bit comparisons required by quickselect
- Distributional Convergence for the Number of Symbol Comparisons Used by Quickselect
- QuickSelect Tree Process Convergence, With an Application to Distributional Convergence for the Number of Symbol Comparisons Used by Worst-Case Find
- On a Constant Arising in the Analysis of Bit Comparisons in Quickselect
- The Number of Symbol Comparisons in QuickSort and QuickSelect
- Quicksort with Equal Keys
- Uncommon suffix tries
- Towards a Realistic Analysis of Some Popular Sorting Algorithms
- Increasing the efficiency of quicksort
- On Some Useful "Inefficient" Statistics
- Quicksort
