Towards a realistic analysis of the QuickSelect algorithm

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

zbMATH Keywords

permutationsselection probleminformation theoryasymptotic estimatespattern matchingprobabilistic analysis of algorithmsQuickselectRice's methodsorting and searching algorithms

Mathematics Subject Classification ID

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 (3)

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

• Quicksort

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

This page was built for publication: Towards a realistic analysis of the QuickSelect algorithm