Hoare's Selection Algorithm: A Markov Chain Approach
From MaRDI portal
Publication:4393823
DOI10.1239/jap/1032192549zbMath0913.60059OpenAlexW2007046591MaRDI QIDQ4393823
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
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