The analysis of range quickselect and related problems

DOI10.1016/j.tcs.2011.06.030zbMath1227.68117OpenAlexW2066781846WikidataQ38881243 ScholiaQ38881243MaRDI QIDQ650886

Conrado Martínez, Alois Panholzer, Prodinger, Helmut

Publication date: 7 December 2011

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2011.06.030

zbMATH Keywords

average-case analysisbinary search treesquickselectmovesHoare's Findrange quickselect

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Searching and sorting (68P10) Randomized algorithms (68W20)

Uses Software

• Quicksort
• Find

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Multiple Quickselect -- Hoare's Find algorithm for several elements
• On quickselect, partial sorting and multiple Quickselect
• Moves and displacements of particular elements in quicksort
• Linear probing and graphs
• On the number of descendants and ascendants in random search trees
• The contraction method for recursive algorithms
• Distribution of distances in random binary search trees.
• Randomized search trees
• Adaptive sampling strategies for quickselects
• Analysis of Hoare's FIND algorithm with Median-of-three partition
• Quickselect and the Dickman Function
• Comparisons in Hoare's Find Algorithm
• Distances and Finger Search in Random Binary Search Trees
• Analysis of quickselect : an algorithm for order statistics
• Asymptotic distribution theory for Hoare's selection algorithm
• Average-case analysis of moves in Quick Select
• Quicksort
• On the probabilistic worst-case time of ``find

This page was built for publication: The analysis of range quickselect and related problems