Asymptotic distribution theory for Hoare's selection algorithm
From MaRDI portal
Publication:4877468
DOI10.2307/1427920zbMath0853.60033OpenAlexW2316865302MaRDI QIDQ4877468
Publication date: 5 January 1997
Published in: Advances in Applied Probability (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.2307/1427920
random environmentstochastic algorithmrandom walk in random environmentquicksort-type selection algorithmrandom binary number
Searching and sorting (68P10) Special processes (60K99) Functional limit theorems; invariance principles (60F17)
Related Items (29)
Stability of perpetuities ⋮ On the median-of-k version of Hoare's selection algorithm ⋮ Simulating the Dickman distribution ⋮ The Weighted Branching Process ⋮ QuickSelect Tree Process Convergence, With an Application to Distributional Convergence for the Number of Symbol Comparisons Used by Worst-Case Find ⋮ Exact simulation of generalised Vervaat perpetuities ⋮ Density functions for \texttt{QuickQuant} and \texttt{QuickVal} ⋮ Almost sure convergence to the quicksort process ⋮ Multivariate linear recursions with Markov-dependent coefficients ⋮ The quicksort process ⋮ Analysis of the expected number of bit comparisons required by quickselect ⋮ Process convergence for the complexity of radix selection on Markov sources ⋮ The analysis of range quickselect and related problems ⋮ A general limit theorem for recursive algorithms and combinatorial structures ⋮ Random binary trees: from the average case analysis to the asymptotics of distributions ⋮ Statistical aspects of perpetuities ⋮ The functional equation of the smoothing transform ⋮ 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 ⋮ On the silhouette of binary search trees ⋮ On stochastic recursive equations of sum and max type ⋮ On weighted depths in random binary search trees ⋮ All solutions of the stochastic fixed point equation of the Quicksort process ⋮ Mixed distributions in Sattolo's algorithm for cyclic permutations via randomization and derandomization ⋮ Stochastic fixed-point equations ⋮ Distributional Convergence for the Number of Symbol Comparisons Used by Quickselect ⋮ The Smoothing Transform: A Review of Contraction Results ⋮ Analysis of quickselect under Yaroslavskiy's dual-pivoting algorithm
This page was built for publication: Asymptotic distribution theory for Hoare's selection algorithm
