Hoare's Selection Algorithm: A Markov Chain Approach

DOI10.1239/jap/1032192549zbMath0913.60059OpenAlexW2007046591MaRDI QIDQ4393823

Rudolf Grübel

Publication date: 26 May 1999

Published in: Journal of Applied Probability (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1239/jap/1032192549

zbMATH Keywords

Markov chainsconvergence in distributionstochastic orderingrandomised algorithms

Mathematics Subject Classification ID

Searching and sorting (68P10) Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20)

Related Items (14)

Stability of perpetuities ⋮ On the median-of-k version of Hoare's selection algorithm ⋮ QuickSelect Tree Process Convergence, With an Application to Distributional Convergence for the Number of Symbol Comparisons Used by Worst-Case Find ⋮ Density functions for \texttt{QuickQuant} and \texttt{QuickVal} ⋮ Almost sure convergence to the quicksort process ⋮ Renorming divergent perpetuities ⋮ Random binary trees: from the average case analysis to the asymptotics of distributions ⋮ Statistical aspects of perpetuities ⋮ Distributional analysis of swaps in quick select ⋮ On the number of iterations required by Von Neumann addition ⋮ Mixed Poisson approximation of node depth distributions in random binary search trees ⋮ All solutions of the stochastic fixed point equation of the Quicksort process ⋮ Distributional Convergence for the Number of Symbol Comparisons Used by Quickselect ⋮ Analysis of quickselect under Yaroslavskiy's dual-pivoting algorithm

This page was built for publication: Hoare's Selection Algorithm: A Markov Chain Approach