Optimal sampling strategies in Quicksort and Quickselect

DOI10.1137/S0097539700382108MaRDI QIDQ2784476zbMATH OpenWikidataFDO

Authors Conrado Martínez, Salvador Roura

Publication date 23 April 2002

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

Full work available at URL https://doi.org/10.1137/S0097539700382108

zbMATH Keywords

analysis of algorithmsdivide-and-conquermedian-of-\((2k+1)\)quickselectquicksortsamplingselectionsorting

Mathematics Subject Classification ID

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

Recommendations

• Optimal sampling strategies for quicksort
• Adaptive sampling strategies for quickselects
• Efficient Sampling Allocation Procedures for Optimal Quantile Selection
• On the variance of quickselect
• Towards a realistic analysis of the QuickSelect algorithm
• Fast sampling of perfectly uniform satisfying assignments
• Resilient quicksort and selection
• Efficient sampling of random permutations

Cited in

(21)

• Fault tolerant sorting -- theoretical and empirical analyses of the randomized quickmergesort algorithm
• Transitional behaviors of the average cost of quicksort with median-of-\((2t+1)\)
• Almost sure convergence to the quicksort process
• QuickXsort: a fast sorting scheme in theory and practice
• The quicksort process
• On Floyd and Rivest's SELECT algorithm
• Analysis of quickselect under Yaroslavskiy's dual-pivoting algorithm
• Adaptive sampling strategies for quickselects
• Analysis of pivot sampling in dual-pivot Quicksort: a holistic analysis of Yaroslavskiy's partitioning scheme
• BlockQuicksort: avoiding branch mispredictions in Quicksort
• Multikey quickselect
• Optimal sampling strategies for quicksort
• scientific article; zbMATH DE number 7359768 (Why is no real title available?)
• Sesquickselect: one and a half pivots for cache-efficient selection
• Finding a mediocre player
• scientific article; zbMATH DE number 7765400 (Why is no real title available?)
• On the (k, r)-Quicksort on the fly process
• Distributed optimal coverage control in multi-agent systems: known and unknown environments
• Efficient sample sort and the average case analysis of PEsort
• Weighted height of random trees
• Computing inversion pair cardinality through partition-based sorting

This page was built for publication: Optimal sampling strategies in Quicksort and Quickselect

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2784476)