Almost sure convergence to the quicksort process

DOI10.1016/J.SPA.2020.03.008zbMath1455.60052OpenAlexW3012638128MaRDI QIDQ2196368

Uwe Roesler

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) Special processes (60K99) Functional limit theorems; invariance principles (60F17)

Cites Work

• Some asymptotic theory for the bootstrap
• A fixed point theorem for distributions
• A characterization of the set of fixed points of the quicksort transformation
• The contraction method for recursive algorithms
• The quicksort process
• Optimal Sampling Strategies in Quicksort and Quickselect
• Analysis of Hoare's FIND algorithm with Median-of-three partition
• A limiting distribution for quicksort
• Hoare's Selection Algorithm: A Markov Chain Approach
• Asymptotic distribution theory for Hoare's selection algorithm
• A limit theorem for “quicksort”
• Quicksort
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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