Optimal Sampling Strategies in Quicksort and Quickselect

DOI10.1137/S0097539700382108zbMath0996.68038WikidataQ56533175 ScholiaQ56533175MaRDI QIDQ2784476

Salvador Roura, Conrado Martínez

Publication date: 23 April 2002

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

samplingsortingselectionanalysis of algorithmsquickselectquicksortdivide-and-conquermedian-of-\((2k+1)\)

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Searching and sorting (68P10) Nonnumerical algorithms (68W05)

Related Items

Analysis of pivot sampling in dual-pivot Quicksort: a holistic analysis of Yaroslavskiy's partitioning scheme, Efficient sample sort and the average case analysis of PEsort, Unnamed Item, Almost sure convergence to the quicksort process, The quicksort process, Unnamed Item, Multikey quickselect, BlockQuicksort, Weighted height of random trees, QuickHeapsort: modifications and improved analysis, Computing inversion pair cardinality through partition-based sorting, QuickXsort: a fast sorting scheme in theory and practice, Finding a mediocre player, Fault tolerant sorting -- theoretical and empirical analyses of the randomized quickmergesort algorithm, On Floyd and Rivest's SELECT algorithm, Analysis of quickselect under Yaroslavskiy's dual-pivoting algorithm