A limit theorem for “quicksort”

DOI10.1051/ita/1991250100851zbMath0718.68026OpenAlexW1511251174MaRDI QIDQ5750394

Publication date: 1991

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/92383

zbMATH Keywords

Quicksort

Mathematics Subject Classification ID

Searching and sorting (68P10)

Related Items (87)

Distribution of a class of divide and conquer recurrences arising from the computation of the Walsh-Hadamard transform ⋮ Distribution of distances in random binary search trees. ⋮ Limit laws for partial match queries in quadtrees ⋮ Weakly protected nodes in random binary search trees ⋮ One-sided variations on binary search trees ⋮ On Tail Bounds for Random Recursive Trees ⋮ On the contraction method with degenerate limit equation. ⋮ The Weighted Branching Process ⋮ Distances in random digital search trees ⋮ Some properties of a limiting distribution in Quicksort ⋮ Inversions in split trees and conditional Galton--Watson trees ⋮ The left-right-imbalance of binary search trees ⋮ Squaring within the Colless index yields a better balance index ⋮ Thin tails of fixed points of the nonhomogeneous smoothing transform ⋮ Logarithmic integrals, zeta values, and tiered binomial coefficients ⋮ Average-case analysis of multiple Quickselect: An algorithm for finding order statistics ⋮ Higher moments of Banach space valued random variables ⋮ A limit process for partial match queries in random quadtrees and 2-d trees ⋮ Limit laws for two distance-based indices in random recursive tree models ⋮ On the size of paged recursive trees ⋮ Unnamed Item ⋮ Fixed points of the smoothing transform: two-sided solutions ⋮ Analysis of quickselect : an algorithm for order statistics ⋮ DEGREE PROFILE OF HIERARCHICAL LATTICE NETWORKS ⋮ Almost sure convergence to the quicksort process ⋮ Analysis of a drop-push model for percolation and coagulation ⋮ General Edgeworth expansions with applications to profiles of random trees ⋮ The quicksort process ⋮ Distributional convergence for the number of symbol comparisons used by QuickSort ⋮ Limit distribution of the quartet balance index for Aldous’s $(\beta \ge 0)$-model ⋮ Exact and approximate limit behaviour of the Yule tree's cophenetic index ⋮ Analysis of the expected number of bit comparisons required by quickselect ⋮ On densities for solutions to stochastic fixed point equations ⋮ On the tails of the limiting QuickSort density ⋮ On the number of jumps of random walks with a barrier ⋮ A general limit theorem for recursive algorithms and combinatorial structures ⋮ Minimal clade size and external branch length under the neutral coalescent ⋮ Search trees: metric aspects and strong limit theorems ⋮ Random binary trees: from the average case analysis to the asymptotics of distributions ⋮ On the number of segregating sites for populations with large family sizes ⋮ On the Variety of Shapes on the Fringe of a Random Recursive Tree ⋮ Asymptotic distributions for random median quicksort ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A fixed point theorem for distributions ⋮ Asymptotic Properties of a Leader Election Algorithm ⋮ Cost functionals for large (uniform and simply generated) random trees ⋮ General combinatorial schemas: Gaussian limit distributions and exponential tails ⋮ Perpetuities in Fair Leader Election Algorithms ⋮ The functional equation of the smoothing transform ⋮ The total path length of split trees ⋮ Distributional analysis of swaps in quick select ⋮ On martingale tail sums for the path length in random trees ⋮ On statistical tests of phylogenetic tree imbalance: The Sackin and other indices revisited ⋮ Limiting distributions for additive functionals on Catalan trees ⋮ On the number of iterations required by Von Neumann addition ⋮ Approximating the limiting Quicksort distribution ⋮ On a multivariate contraction method for random recursive structures with applications to Quicksort ⋮ On the silhouette of binary search trees ⋮ On stochastic recursive equations of sum and max type ⋮ A limit field for orthogonal range searches in two-dimensional random point search trees ⋮ The mean, variance and limiting distribution of two statistics sensitive to phylogenetic tree balance ⋮ Asymptotic joint normality of counts of uncorrelated motifs in recursive trees ⋮ On weighted depths in random binary search trees ⋮ On the internal path length ofd-dimensional quad trees ⋮ All solutions of the stochastic fixed point equation of the Quicksort process ⋮ An almost sure result for path lengths in binary search trees ⋮ Limit laws for the Randić index of random binary tree models ⋮ Inversions in Split Trees and Conditional Galton–Watson Trees ⋮ A note concerning the limit distribution of the quicksort algorithm ⋮ Split trees -- a unifying model for many important random trees of logarithmic height: a brief survey ⋮ One-sided variations on interval trees ⋮ Stochastic fixed-point equations ⋮ Convergence of the population dynamics algorithm in the Wasserstein metric ⋮ QuickSort: improved right-tail asymptotics for the limiting distribution, and large deviations ⋮ Partial match queries in random quadtrees ⋮ Distributional Convergence for the Number of Symbol Comparisons Used by Quickselect ⋮ Limit Theorems for Depths and Distances in Weighted Random B-Ary Recursive Trees ⋮ Limit distribution of distances in biased random tries ⋮ Random additions in urns of integers ⋮ On weighted branching processes in random environment. ⋮ The dual tree of a recursive triangulation of the disk ⋮ Probabilistic analysis of a genealogical model of animal group patterns ⋮ The Smoothing Transform: A Review of Contraction Results ⋮ On a functional contraction method ⋮ Analysis of quickselect under Yaroslavskiy's dual-pivoting algorithm ⋮ On binary search tree recursions with monomials as toll functions

Uses Software

Quicksort

Cites Work

This page was built for publication: A limit theorem for “quicksort”