Towards a realistic analysis of the QuickSelect algorithm

DOI10.1007/S00224-015-9633-5MaRDI QIDQ290901zbMATH OpenOpenAlexFDO

Authors Julien Clément, James Allen Fill, Thu Hien Nguyen Thi, Brigitte Vallée

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

permutationsasymptotic estimatesinformation theorypattern matchingselection problemprobabilistic analysis of algorithmsQuickselectRice's methodsorting and searching algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Searching and sorting (68P10)

Recommendations

• Distributional convergence for the number of symbol comparisons used by QuickSelect
• The Number of Symbol Comparisons in QuickSort and QuickSelect
• Distributional convergence for the number of symbol comparisons used by QuickSort (extended abstract)
• A general framework for the realistic analysis of sorting and searching algorithms. Application to some popular algorithms
• Analysis of quickselect : an algorithm for order statistics

Cites work

• scientific article; zbMATH DE number 3886512 (Why is no real title available?)
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 815575 (Why is no real title available?)
• A general framework for the realistic analysis of sorting and searching algorithms. Application to some popular algorithms
• Analytic combinatorics
• Data-specific analysis of string sorting
• Distributional convergence for the number of symbol comparisons used by QuickSelect
• Dynamical sources in information theory: A general analysis of trie structures
• Dynamical sources in information theory: Fundamental intervals and word prefixes
• Increasing the efficiency of quicksort
• Mellin transforms and asymptotics: Finite differences and Rice's integrals
• On Some Useful "Inefficient" Statistics
• On a Constant Arising in the Analysis of Bit Comparisons in Quickselect
• Quickselect tree process convergence, with an application to distributional convergence for the number of symbol comparisons used by worst-case find
• Quicksort
• Quicksort with Equal Keys
• The Number of Symbol Comparisons in QuickSort and QuickSelect
• Towards a realistic analysis of some popular sorting algorithms
• Uncommon suffix tries

Cited in

(11)

• Probabilistic analysis of multiple quick select
• Dichotomic Selection on Words: A Probabilistic Analysis
• Analysis of Branch Misses in Quicksort
• Multikey quickselect
• Optimal sampling strategies in Quicksort and Quickselect
• A general framework for the realistic analysis of sorting and searching algorithms. Application to some popular algorithms
• Towards a realistic analysis of some popular sorting algorithms
• Asymptotic analysis of an optimized quicksort algorithm.
• The depoissonisation quintet: Rice-Poisson-Mellin-Newton-Laplace
• Distributional convergence for the number of symbol comparisons used by QuickSelect
• Process convergence for the complexity of radix selection on Markov sources

Describes a project that uses

Uses Software

• Quicksort

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q290901)