Analysis of quickselect under Yaroslavskiy's dual-pivoting algorithm

DOI10.1007/S00453-014-9953-XzbMath1336.68052arXiv1306.3819OpenAlexW2067982019MaRDI QIDQ261384

Sebastian Wild, Markus E. Nebel, Hosam M. Mahmoud

Publication date: 23 March 2016

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1306.3819

zbMATH Keywords

contractionaverage-case analysisgrand averagequickselectquicksort

Mathematics Subject Classification ID

Searching and sorting (68P10) Combinatorial probability (60C05) Information storage and retrieval of data (68P20)

Related Items (1)

Analysis of pivot sampling in dual-pivot Quicksort: a holistic analysis of Yaroslavskiy's partitioning scheme

Uses Software

• Quicksort
• Find
• MaLiJAn

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Multiple Quickselect -- Hoare's Find algorithm for several elements
• On distributional properties of perpetuities
• Distributional analysis of swaps in quick select
• Moves and displacements of particular elements in quicksort
• The analysis of Quicksort programs
• A general limit theorem for recursive algorithms and combinatorial structures
• The contraction method for recursive algorithms
• On the analysis of stochastic divide and conquer algorithms
• Average-case analysis of multiple Quickselect: An algorithm for finding order statistics
• Distributional convergence for the number of symbol comparisons used by QuickSort
• Analysis of the expected number of bit comparisons required by quickselect
• On a multivariate contraction method for random recursive structures with applications to Quicksort
• Optimal Sampling Strategies in Quicksort and Quickselect
• Average Case Analysis of Java 7’s Dual Pivot Quicksort
• Adaptive sampling strategies for quickselects
• Quickselect and the Dickman Function
• Combinatorial analysis of quicksort algorithm
• Comparisons in Hoare's Find Algorithm
• Hoare's Selection Algorithm: A Markov Chain Approach
• A generating functions approach for the analysis of grand averages for multiple QUICKSELECT
• Probability metrics and recursive algorithms
• Analysis of quickselect : an algorithm for order statistics
• Asymptotic distribution theory for Hoare's selection algorithm
• Average Case and Distributional Analysis of Dual-Pivot Quicksort
• Optimal Partitioning for Dual Pivot Quicksort
• A limit theorem for “quicksort”
• Quicksort

This page was built for publication: Analysis of quickselect under Yaroslavskiy's dual-pivoting algorithm