Average-case analysis of multiple Quickselect: An algorithm for finding order statistics
From MaRDI portal
Publication:1922133
DOI10.1016/0167-7152(95)00139-5zbMath0854.62052OpenAlexW2026693728MaRDI QIDQ1922133
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
sortinganalysis of algorithmsQuickselectrandom binary search treeQuicksortselection of order statistics
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
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