Asymptotic distributions for random median quicksort

DOI10.1016/J.JDA.2006.07.003MaRDI QIDQ2466023zbMATH OpenOpenAlexFDO

Authors Hassan M. Okasha, Uwe Rösler

Publication date 11 January 2008

Published in Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jda.2006.07.003

zbMATH Keywords

analysis of algorithmcontraction methoddivide-and-conquer algorithmEuler differential equationquicksortrecursive equationsorting algorithmstochastic fixed point equation

Mathematics Subject Classification ID

Asymptotic distribution theory in statistics (62E20) Searching and sorting (68P10) Analysis of algorithms (68W40)

Recommendations

• Approximating the limiting quicksort distribution
• QuickSort: improved right-tail asymptotics for the limiting distribution, and large deviations
• A limiting distribution for quicksort
• A note concerning the limit distribution of the quicksort algorithm
• On the tails of the limiting Quicksort distribution
• QuickSort: Improved right-tail asymptotics for the limiting distribution, and large deviations (Extended Abstract)
• A note on the Quicksort asymptotics
• Large Deviations for Quicksort

Cites work

• A fixed point theorem for distributions
• A limit theorem for “quicksort”
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 1052336 (Why is no real title available?)
• scientific article; zbMATH DE number 815575 (Why is no real title available?)
• Increasing the efficiency of quicksort
• On the analysis of stochastic divide and conquer algorithms
• Quicksort
• Some asymptotic theory for the bootstrap
• The analysis of Quicksort programs
• The contraction method for recursive algorithms

Cited in

(8)

• Transitional behaviors of the average cost of quicksort with median-of-\((2t+1)\)
• On the analysis of stochastic divide and conquer algorithms
• A simple expected running time analysis for randomized ``divide and conquer algorithms
• On a multivariate contraction method for random recursive structures with applications to quicksort
• QUICKSELECT revisited
• scientific article; zbMATH DE number 1305472 (Why is no real title available?)
• scientific article; zbMATH DE number 1052336 (Why is no real title available?)
• On the (k, r)-Quicksort on the fly process

Describes a project that uses

Uses Software

• Quicksort

This page was built for publication: Asymptotic distributions for random median quicksort

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