Almost sure convergence to the quicksort process

DOI10.1016/J.SPA.2020.03.008MaRDI QIDQ2196368zbMATHOpenAlexFDO

Authors Uwe Rösler

Publication date 2 September 2020

Published in Stochastic Processes and their Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.spa.2020.03.008

zbMATH Keywords

stochastic processesanalysis of algorithmsSkorokhod convergencestochastic fixed point equationweighted branching processquicksort process

Mathematics Subject Classification ID

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

Recommendations

• The quicksort process
• Quicksort asymptotics
• A limit theorem for “quicksort”
• Rates of convergence for Quicksort
• Approximating the limiting quicksort distribution

Cites work

• scientific article; zbMATH DE number 193012 (Why is no real title available?)
• scientific article; zbMATH DE number 1354815 (Why is no real title available?)
• scientific article; zbMATH DE number 1033192 (Why is no real title available?)
• scientific article; zbMATH DE number 815575 (Why is no real title available?)
• scientific article; zbMATH DE number 3410334 (Why is no real title available?)
• A characterization of the set of fixed points of the quicksort transformation
• A fixed point theorem for distributions
• A limit theorem for “quicksort”
• A limiting distribution for quicksort
• Analysis of Hoare's FIND algorithm with Median-of-three partition
• Asymptotic distribution theory for Hoare's selection algorithm
• Hoare's Selection Algorithm: A Markov Chain Approach
• Optimal sampling strategies in Quicksort and Quickselect
• Partial Quicksort and Quickpartitionsort
• Quicksort
• Some asymptotic theory for the bootstrap
• The analysis of Find and versions of it
• The contraction method for recursive algorithms
• The quicksort process

Cited in

(2)

• Partial Quicksort and Quickpartitionsort
• The quicksort process

This page was built for publication: Almost sure convergence to the quicksort process

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