𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Large Deviations for Quicksort

✍ Scribed by C.J.H. McDiarmid; R.B. Hayward

Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
300 KB
Volume
21
Category
Article
ISSN
0196-6774

No coin nor oath required. For personal study only.

✦ Synopsis

Let Q be the random number of comparisons made by quicksort in sorting n n distinct keys when we assume that all n! possible orderings are equally likely. Known results concerning moments for Q do not show how rare it is for Q to n n make large deviations from its mean. Here we give a good approximation to the probability of such a large deviation and find that this probability is quite small. As well as the basic quicksort, we consider the variant in which the partitioning key is Ε½ . chosen as the median of 2 t q 1 keys.

πŸ“œ SIMILAR VOLUMES

Large Deviations Asymptotics for Spheric
Large Deviations Asymptotics for Spherical Integrals
✍ Alice Guionnet; Ofer Zeitouni πŸ“‚ Article πŸ“… 2002 πŸ› Elsevier Science 🌐 English βš– 554 KB

Consider the spherical integral , where m b N denote the Haar measure on the orthogonal group O N when b=1 and on the unitary group U N when b=2, and D N , E N are diagonal real matrices whose spectral measures converge to m D , m E . In this paper we prove the existence and represent as solution t

A killer adversary for quicksort
A killer adversary for quicksort
✍ M. D. McIlroy πŸ“‚ Article πŸ“… 1999 πŸ› John Wiley and Sons 🌐 English βš– 32 KB

Quicksort can be made to go quadratic by constructing input on-the-fly in response to the sequence of items compared. The technique is illustrated by a specific adversary for the standard C qsort function. The general method works against any implementation of quicksort -even a randomizing one -that