Towards a realistic analysis of the QuickSelect algorithm

DOI10.1007/S00224-015-9633-5zbMATH Open1341.68035OpenAlexW1145223112MaRDI QIDQ290901FDOQ290901

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

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

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)

Cites Work

• Quicksort
• Title not available (Why is that?)
• Title not available (Why is that?)
• On Some Useful "Inefficient" Statistics
• Dynamical sources in information theory: Fundamental intervals and word prefixes
• Analysis of the expected number of bit comparisons required by quickselect
• Title not available (Why is that?)
• Mellin transforms and asymptotics: Finite differences and Rice's integrals
• Title not available (Why is that?)
• Dynamical sources in information theory: A general analysis of trie structures
• Distributional convergence for the number of symbol comparisons used by QuickSelect
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• Increasing the efficiency of quicksort

Cited In (7)

• Dichotomic Selection on Words: A Probabilistic Analysis
• Probabilistic analysis of multiple quick select
• The Depoissonisation quintet: Rice-Poisson-Mellin-Newton-Laplace
• Analysis of Branch Misses in Quicksort
• Optimal sampling strategies in Quicksort and Quickselect
• Asymptotic analysis of an optimized quicksort algorithm.
• Process convergence for the complexity of radix selection on Markov sources

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)