A limiting distribution for quicksort
RAIRO-Theor. Inf. Appl., 23 3 (1989) 335-343
Published online: 2017-02-01
Articles citing this article
The Citing articles tool gives a list of articles citing the current article.
The citing articles come from EDP Sciences database, as well as other publishers participating in CrossRef Cited-by Linking Program. You can set up your personal account to receive an email alert each time this article is cited by a new article (see the menu on the right-hand side of the abstract page).
Cited article:
This article has been cited by the following article(s):
The Sackin index and depth of leaves in generalized Schröder trees
Panpan Zhang and Hosam MahmoudStochastic Models 41 (2) 208 (2025)
https://doi.org/10.1080/15326349.2024.2353061
Shape parameters of evolutionary trees in theoretical computer science
Michael FuchsPhilosophical Transactions of the Royal Society B: Biological Sciences 380 (1919) (2025)
https://doi.org/10.1098/rstb.2023.0304
Balancing m-ary search trees with compressions on the fringe
Shuyang Gao, Leen Hatem and Hosam MahmoudActa Informatica 61 (1) 53 (2024)
https://doi.org/10.1007/s00236-023-00448-2
Logarithmic integrals, zeta values, and tiered binomial coefficients
Michael E. Hoffman and Markus KubaMonatshefte für Mathematik 195 (1) 119 (2021)
https://doi.org/10.1007/s00605-021-01533-9
Algorithms and Complexity
Ioana O. Bercea and Guy EvenLecture Notes in Computer Science, Algorithms and Complexity 12701 116 (2021)
https://doi.org/10.1007/978-3-030-75242-2_8
Upper tail analysis of bucket sort and random tries
Ioana O. Bercea and Guy EvenTheoretical Computer Science 895 55 (2021)
https://doi.org/10.1016/j.tcs.2021.09.029
Almost sure convergence to the Quicksort process
Uwe RoeslerStochastic Processes and their Applications 130 (9) 5290 (2020)
https://doi.org/10.1016/j.spa.2020.03.008
Stochastic fixed-point equations
Uwe RoeslerStochastic Models 35 (3) 238 (2019)
https://doi.org/10.1080/15326349.2019.1578242
On densities for solutions to stochastic fixed point equations
Kevin LeckeyRandom Structures & Algorithms 54 (3) 528 (2019)
https://doi.org/10.1002/rsa.20799
QuickSort: improved right-tail asymptotics for the limiting distribution, and large deviations
James Allen Fill and Wei-Chun HungElectronic Journal of Probability 24 (none) (2019)
https://doi.org/10.1214/19-EJP331
Analyzing randomized search heuristics via stochastic domination
Benjamin DoerrTheoretical Computer Science 773 115 (2019)
https://doi.org/10.1016/j.tcs.2018.09.024
Arbres pour l’Algorithmique
Brigitte Chauvin, Julien Clément and Danièle GardyMathématiques et Applications, Arbres pour l’Algorithmique 83 217 (2018)
https://doi.org/10.1007/978-3-319-93725-0_6
On Weighted Depths in Random Binary Search Trees
Rafik Aguech, Anis Amri and Henning SulzbachJournal of Theoretical Probability 31 (4) 1929 (2018)
https://doi.org/10.1007/s10959-017-0773-1
Exact and approximate limit behaviour of the Yule tree’s cophenetic index
Krzysztof BartoszekMathematical Biosciences 303 26 (2018)
https://doi.org/10.1016/j.mbs.2018.05.005
Cost functionals for large (uniform and simply generated) random trees
Jean-François Delmas, Jean-Stéphane Dhersin and Marion SciauveauElectronic Journal of Probability 23 (none) (2018)
https://doi.org/10.1214/18-EJP213
(2017)
https://doi.org/10.1101/120931
Analysis of the Multi-Pivot Quicksort Process
Mahmoud Ragab, Beih El-Sayed El-Desouky and Nora NaderOpen Journal of Modelling and Simulation 05 (01) 47 (2017)
https://doi.org/10.4236/ojmsi.2017.51004
General Edgeworth expansions with applications to profiles of random trees
Zakhar Kabluchko, Alexander Marynych and Henning SulzbachThe Annals of Applied Probability 27 (6) (2017)
https://doi.org/10.1214/17-AAP1285
On martingale tail sums for the path length in random trees
Henning SulzbachRandom Structures & Algorithms 50 (3) 493 (2017)
https://doi.org/10.1002/rsa.20674
A functional central limit theorem for branching random walks, almost sure weak convergence and applications to random trees
Rudolf Grübel and Zakhar KabluchkoThe Annals of Applied Probability 26 (6) (2016)
https://doi.org/10.1214/16-AAP1188
Branching Processes and Their Applications
Uwe RoeslerLecture Notes in Statistics, Branching Processes and Their Applications 219 219 (2016)
https://doi.org/10.1007/978-3-319-31641-3_13
On the Convergence of the Dual-Pivot Quicksort Process
Mahmoud Ragab, Beih El-Sayed El-Desouky and Nora NaderOpen Journal of Modelling and Simulation 04 (01) 1 (2016)
https://doi.org/10.4236/ojmsi.2016.41001
Average Case and Distributional Analysis of Dual-Pivot Quicksort
Sebastian Wild, Markus E. Nebel and Ralph NeiningerACM Transactions on Algorithms 11 (3) 1 (2015)
https://doi.org/10.1145/2629340
Refined quicksort asymptotics
Ralph NeiningerRandom Structures & Algorithms 46 (2) 346 (2015)
https://doi.org/10.1002/rsa.20497
A note on the quicksort asymptotics
Michael FuchsRandom Structures & Algorithms 46 (4) 677 (2015)
https://doi.org/10.1002/rsa.20524
Search trees: Metric aspects and strong limit theorems
Rudolf GrübelThe Annals of Applied Probability 24 (3) (2014)
https://doi.org/10.1214/13-AAP948
https://doi.org/10.1002/9781118445112.stat00449
The Quicksort process
Mahmoud Ragab and Uwe RoeslerStochastic Processes and their Applications 124 (2) 1036 (2014)
https://doi.org/10.1016/j.spa.2013.09.014
Distributional Convergence for the Number of Symbol Comparisons Used by Quickselect
James Allen Fill and Takehiko NakamaAdvances in Applied Probability 45 (2) 425 (2013)
https://doi.org/10.1239/aap/1370870125
Mathematical and Engineering Methods in Computer Science
Colin McDiarmidLecture Notes in Computer Science, Mathematical and Engineering Methods in Computer Science 7721 43 (2013)
https://doi.org/10.1007/978-3-642-36046-6_5
Distributional convergence for the number of symbol comparisons used by QuickSort
James Allen FillThe Annals of Applied Probability 23 (3) (2013)
https://doi.org/10.1214/12-AAP866
Distributional Convergence for the Number of Symbol Comparisons Used by Quickselect
James Allen Fill and Takehiko NakamaAdvances in Applied Probability 45 (02) 425 (2013)
https://doi.org/10.1017/S000186780000639X
The total path length of split trees
Nicolas Broutin and Cecilia HolmgrenThe Annals of Applied Probability 22 (5) (2012)
https://doi.org/10.1214/11-AAP812
On the Asymptotic Internal Path Length and the Asymptotic Wiener Index of Random Split Trees
Goetz Olaf MunsoniusElectronic Journal of Probability 16 (none) (2011)
https://doi.org/10.1214/EJP.v16-889
Analysis of the Expected Number of Bit Comparisons Required by Quickselect
James Allen Fill and Takéhiko NakamaAlgorithmica 58 (3) 730 (2010)
https://doi.org/10.1007/s00453-009-9294-3
On the silhouette of binary search trees
Rudolf GrübelThe Annals of Applied Probability 19 (5) (2009)
https://doi.org/10.1214/08-AAP593
Distribution of a class of divide and conquer recurrences arising from the computation of the Walsh–Hadamard transform
Paweł Hitczenko, Jeremy R. Johnson and Hung-Jen HuangTheoretical Computer Science 352 (1-3) 8 (2006)
https://doi.org/10.1016/j.tcs.2005.09.074
Zufällige binäre Bäume: Von der average-case Analyse zur Verteilungsasymptotik
Rudolf GrübelMathematische Semesterberichte 53 (2) 210 (2006)
https://doi.org/10.1007/s00591-006-0001-z
Minimal clade size and external branch length under the neutral coalescent
Michael G. B. Blum and Olivier FrançoisAdvances in Applied Probability 37 (03) 647 (2005)
https://doi.org/10.1017/S0001867800000409
Minimal clade size and external branch length under the neutral coalescent
Michael G. B. Blum and Olivier FrançoisAdvances in Applied Probability 37 (3) 647 (2005)
https://doi.org/10.1239/aap/1127483740
Interacting Stochastic Systems
Ralph Neininger and Ludger RüschendorfInteracting Stochastic Systems 435 (2005)
https://doi.org/10.1007/3-540-27110-4_20
https://doi.org/10.1002/0471667196.ess1142.pub2
Stochastic analysis of tree–like data structures
Michael DrmotaProceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences 460 (2041) 271 (2004)
https://doi.org/10.1098/rspa.2003.1243
https://doi.org/10.1002/0471667196.ess1142
An almost sure result for path lengths in binary search trees
F. M. Dekking and L. E. MeesterAdvances in Applied Probability 35 (2) 363 (2003)
https://doi.org/10.1239/aap/1051201652
An almost sure result for path lengths in binary search trees
F. M. Dekking and L. E. MeesterAdvances in Applied Probability 35 (02) 363 (2003)
https://doi.org/10.1017/S0001867800012295
Density approximation and exact simulation of random variables that are solutions of fixed-point equations
Luc Devroye and Ralph NeiningerAdvances in Applied Probability 34 (02) 441 (2002)
https://doi.org/10.1017/S0001867800011642
Density approximation and exact simulation of random variables that are solutions of fixed-point equations
Luc Devroye and Ralph NeiningerAdvances in Applied Probability 34 (2) 441 (2002)
https://doi.org/10.1239/aap/1025131226
Phase Change of Limit Laws in the Quicksort Recurrence under Varying Toll Functions
Hsien-Kuei Hwang and Ralph NeiningerSIAM Journal on Computing 31 (6) 1687 (2002)
https://doi.org/10.1137/S009753970138390X
https://doi.org/10.1002/9781118032770.biblio
The contraction method for recursive algorithms
U. Rösler and L. RüschendorfAlgorithmica 29 (1-2) 3 (2001)
https://doi.org/10.1007/BF02679611
On a multivariate contraction method for random recursive structures with applications to Quicksort
Ralph NeiningerRandom Structures & Algorithms 19 (3-4) 498 (2001)
https://doi.org/10.1002/rsa.10010
Approximating the limiting Quicksort distribution
James Allen Fill and Svante JansonRandom Structures & Algorithms 19 (3-4) 376 (2001)
https://doi.org/10.1002/rsa.10007
https://doi.org/10.1002/9781118032886.biblio
Mathematics and Computer Science
F. M. Dekking, S. De Graaf and L. E. MeesterMathematics and Computer Science 31 (2000)
https://doi.org/10.1007/978-3-0348-8405-1_3
Mathematics and Computer Science
James Allen Fill and Svante JansonMathematics and Computer Science 53 (2000)
https://doi.org/10.1007/978-3-0348-8405-1_5
Perfect Simulation from the Quicksort Limit Distribution
Luc Devroye, James Fill and Ralph NeiningerElectronic Communications in Probability 5 (none) (2000)
https://doi.org/10.1214/ECP.v5-1024
On the internal path length ofd-dimensional quad trees
Ralph Neininger and Ludger R�schendorfRandom Structures and Algorithms 15 (1) 25 (1999)
https://doi.org/10.1002/(SICI)1098-2418(199908)15:1<25::AID-RSA2>3.0.CO;2-R
Randomization and Approximation Techniques in Computer Science
Charles Knessl and Wojciech SzpankowskiLecture Notes in Computer Science, Randomization and Approximation Techniques in Computer Science 1518 346 (1998)
https://doi.org/10.1007/3-540-49543-6_27
Average-case analysis of multiple Quickselect: An algorithm for finding order statistics
Janice Lent and Hosam M. MahmoudStatistics & Probability Letters 28 (4) 299 (1996)
https://doi.org/10.1016/0167-7152(95)00139-5
A note concerning the limit distribution of the quicksort algorithm
Michael CramerRAIRO - Theoretical Informatics and Applications 30 (3) 195 (1996)
https://doi.org/10.1051/ita/1996300301951
Some properties of a limiting distribution in Quicksort
Kok Hooi Tan and Petros HadjicostasStatistics & Probability Letters 25 (1) 87 (1995)
https://doi.org/10.1016/0167-7152(94)00209-Q
Analysis of quickselect : an algorithm for order statistics
Hosam M. Mahmoud, Reza Modarres and Robert T. SmytheRAIRO - Theoretical Informatics and Applications 29 (4) 255 (1995)
https://doi.org/10.1051/ita/1995290402551
General combinatorial schemas: Gaussian limit distributions and exponential tails
Philippe Flajolet and Michèle SoriaDiscrete Mathematics 114 (1-3) 159 (1993)
https://doi.org/10.1016/0012-365X(93)90364-Y
Distances in random plane-oriented recursive trees
Hosam M. MahmoudJournal of Computational and Applied Mathematics 41 (1-2) 237 (1992)
https://doi.org/10.1016/0377-0427(92)90252-S
A limit theorem for “quicksort”
Uwe RöslerRAIRO - Theoretical Informatics and Applications 25 (1) 85 (1991)
https://doi.org/10.1051/ita/1991250100851
Automatic average-case analysis of algorithms
Philippe Flajolet, Bruno Salvy and Paul ZimmermannTheoretical Computer Science 79 (1) 37 (1991)
https://doi.org/10.1016/0304-3975(91)90145-R