Asymptotic distribution theory for Hoare's selection algorithm

DOI10.2307/1427920MaRDI QIDQ4877468zbMATH OpenOpenAlexFDO

Authors Rudolf Grübel, Uwe Rösler

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

zbMATH Keywords

quicksort-type selection algorithmrandom binary numberrandom environmentrandom walk in random environmentstochastic algorithm

Mathematics Subject Classification ID

Functional limit theorems; invariance principles (60F17) Special processes (60K99) Searching and sorting (68P10)

Recommendations

• Quickselect and the Dickman Function
• A limiting distribution for quicksort
• A limit theorem for “quicksort”
• Analysis of quickselect : an algorithm for order statistics
• Quickselect tree process convergence, with an application to distributional convergence for the number of symbol comparisons used by worst-case find

Cited in

(35)

• A general limit theorem for recursive algorithms and combinatorial structures
• Process convergence for the complexity of radix selection on Markov sources
• Mixed Poisson approximation of node depth distributions in random binary search trees
• On weighted depths in random binary search trees
• Stability of perpetuities
• Almost sure convergence to the quicksort process
• The quicksort process
• Random binary trees: from the average case analysis to the asymptotics of distributions
• Analysis of quickselect under Yaroslavskiy's dual-pivoting algorithm
• Density functions for \texttt{QuickQuant} and \texttt{QuickVal}
• On the number of iterations required by von Neumann addition
• Distributional convergence for the number of symbol comparisons used by QuickSelect
• The smoothing transform: a review of contraction results
• Quickselect and the Dickman Function
• 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
• Distributional asymptotics in the analysis of algorithms: periodicities and discretization
• On the median-of-k version of Hoare's selection algorithm
• scientific article; zbMATH DE number 579153 (Why is no real title available?)
• Hoare's Selection Algorithm: A Markov Chain Approach
• Mixed distributions in Sattolo's algorithm for cyclic permutations via randomization and derandomization
• scientific article; zbMATH DE number 1361593 (Why is no real title available?)
• Exact simulation of generalised Vervaat perpetuities
• All solutions of the stochastic fixed point equation of the Quicksort process
• Stochastic fixed-point equations
• On stochastic recursive equations of sum and max type
• Statistical aspects of perpetuities
• Multivariate linear recursions with Markov-dependent coefficients
• The analysis of range quickselect and related problems
• On fluctuations of complexity measures for the FIND algorithm
• Convergence of the QuickVal residual
• The functional equation of the smoothing transform
• Simulating the Dickman distribution
• Distributional analysis of swaps in quick select
• On the silhouette of binary search trees

This page was built for publication: Asymptotic distribution theory for Hoare's selection algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4877468)