Optimal sampling strategies for quicksort

DOI10.1002/RSA.3240070403MaRDI QIDQ4858238zbMATH OpenOpenAlexFDO

Authors Catherine C. McGeoch, J. D. Tygar

Publication date 1995

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/rsa.3240070403

zbMATH Keywords

general sampling strategiesQuicksort algorithm

Mathematics Subject Classification ID

Searching and sorting (68P10)

Recommendations

• Optimal sampling strategies in Quicksort and Quickselect
• scientific article; zbMATH DE number 7359768
• Adaptive sampling strategies for quickselects
• scientific article; zbMATH DE number 6469176
• Quicksort is optimal for many equal keys

Cites work

• Finding the median
• Samplesort: A Sampling Approach to Minimal Storage Tree Sorting

Cited in

(12)

• Faster deterministic sorting through better sampling.
• Presorting algorithms: an average-case point of view
• Transitional behaviors of the average cost of quicksort with median-of-\((2t+1)\)
• Optimal sampling strategies in Quicksort and Quickselect
• Adaptive sampling strategies for quickselects
• Exploiting partial order with Quicksort
• The Worst Case Permutation for Median-of-Three Quicksort
• Introspective sorting and selection revisited
• scientific article; zbMATH DE number 7359768 (Why is no real title available?)
• Quicksort is optimal for many equal keys
• Finding a mediocre player
• scientific article; zbMATH DE number 7765400 (Why is no real title available?)

This page was built for publication: Optimal sampling strategies for quicksort

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