Average-case analysis of multiple Quickselect: An algorithm for finding order statistics

DOI10.1016/0167-7152(95)00139-5zbMath0854.62052OpenAlexW2026693728MaRDI QIDQ1922133

Hosam M. Mahmoud, Janice Lent

Publication date: 16 January 1997

Published in: Statistics \& Probability Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0167-7152(95)00139-5

zbMATH Keywords

sortinganalysis of algorithmsQuickselectrandom binary search treeQuicksortselection of order statistics

Mathematics Subject Classification ID

Searching and sorting (68P10) Order statistics; empirical distribution functions (62G30) Graph theory (including graph drawing) in computer science (68R10) Probabilistic methods, stochastic differential equations (65C99)

Related Items

QuickSelect Tree Process Convergence, With an Application to Distributional Convergence for the Number of Symbol Comparisons Used by Worst-Case Find, Analysis of multiple quickselect variants., Analysis of the expected number of bit comparisons required by quickselect, Multiple Quickselect -- Hoare's Find algorithm for several elements, Analysis of swaps in radix selection, Distributional analysis of swaps in quick select, Mixed distributions in Sattolo's algorithm for cyclic permutations via randomization and derandomization, Distributional Convergence for the Number of Symbol Comparisons Used by Quickselect, Analysis of quickselect under Yaroslavskiy's dual-pivoting algorithm, Binary search tree recursions with harmonic toll functions

Uses Software

• Quicksort
• Algorithm 489

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Some properties of a limiting distribution in Quicksort
• Approximation Theorems of Mathematical Statistics
• Limit laws for local counters in random binary search trees
• A limiting distribution for quicksort
• Combinatorial analysis of quicksort algorithm
• How Many Comparisons Does Quicksort Use?
• Analysis of quickselect : an algorithm for order statistics
• Randomized binary search technique
• Small Sample Behavior of Some Robust Linear Estimators of Location
• Sequential Confidence Intervals Based on Rank Tests
• A limit theorem for “quicksort”
• Quicksort