Analysis of quickselect : an algorithm for order statistics

DOI10.1051/ita/1995290402551zbMath0838.68029OpenAlexW192578068MaRDI QIDQ4858843

Hosam M. Mahmoud, Reza Modarres, Robert T. Smythe

Publication date: 27 May 1996

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/92508

zbMATH Keywords

sortingQUICKSELECTQUICKSORT

Mathematics Subject Classification ID

Searching and sorting (68P10) Parallel algorithms in computer science (68W10)

Related Items

Limit laws for partial match queries in quadtrees, Exact simulation of generalised Vervaat perpetuities, Fast perfect simulation of Vervaat perpetuities, Average-case analysis of multiple Quickselect: An algorithm for finding order statistics, Sketching with Kerdock's Crayons: Fast Sparsifying Transforms for Arbitrary Linear Maps, Approximating perpetuities, Density functions for \texttt{QuickQuant} and \texttt{QuickVal}, Analysis of the expected number of bit comparisons required by quickselect, The analysis of range quickselect and related problems, Multikey quickselect, A general limit theorem for recursive algorithms and combinatorial structures, Multiple Quickselect -- Hoare's Find algorithm for several elements, Analysis of swaps in radix selection, Distributional analysis of swaps in quick select, Convergence to type I distribution of the extremes of sequences defined by random difference equation, Mixed distributions in Sattolo's algorithm for cyclic permutations via randomization and derandomization, Distributional Convergence for the Number of Symbol Comparisons Used by Quickselect, A generalised Dickman distribution and the number of species in a negative binomial process model, Analysis of quickselect under Yaroslavskiy's dual-pivoting algorithm

Cites Work

• Exponential bounds for the running time of a selection algorithm
• The analysis of Quicksort programs
• A limiting distribution for quicksort
• Inequalities for E k(X, Y) when the marginals are fixed
• Quicksort with Equal Keys
• Combinatorial analysis of quicksort algorithm
• A limit theorem for “quicksort”
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
• Quicksort
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item