A limiting distribution for quicksort

Mireille Régnier

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1989)

  • Volume: 23, Issue: 3, page 335-343
  • ISSN: 0988-3754

How to cite

top

Régnier, Mireille. "A limiting distribution for quicksort." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 23.3 (1989): 335-343. <http://eudml.org/doc/92338>.

@article{Régnier1989,
author = {Régnier, Mireille},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {quicksort; binary search tree; distribution of the data},
language = {eng},
number = {3},
pages = {335-343},
publisher = {EDP-Sciences},
title = {A limiting distribution for quicksort},
url = {http://eudml.org/doc/92338},
volume = {23},
year = {1989},
}

TY - JOUR
AU - Régnier, Mireille
TI - A limiting distribution for quicksort
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 1989
PB - EDP-Sciences
VL - 23
IS - 3
SP - 335
EP - 343
LA - eng
KW - quicksort; binary search tree; distribution of the data
UR - http://eudml.org/doc/92338
ER -

References

top
  1. [BM85] F. BACCELLI and A. M. MAKOWSKY, Direct martingale arguments for stability : The M/G/1 case, Systems & Control Letters, Vol. 6, 1985, p. 181-186. Zbl0568.60091MR801868
  2. [FE57] W. FELLER, An Introduction to Probability Theory and its Applications, Vol. II, Wiley, 1957. Zbl0077.12201MR88081
  3. [HE87] P. HENNEQUIN, Combinatorial analysis of Quicksort Algorithm, RAIRO, Th. Informatics and Applications (to appear). Zbl0685.68058MR1020477
  4. [H062] C. A. HOARE, Quicksort, Computer Journal, Vol. 5, N° 1, 1962. Zbl0108.13601MR142216
  5. [KN73] D. KNUTH, The Art of Computer Programming, Vol. 3: Sorting and Searching, Addison-Wesley, Reading, Mass., 1973. MR445948
  6. [LO87] G. LOUCHARD, Exact and Asymptotic Distributions in Digital and Binary Seach Trees, RAIRO, Th. Informatics and Applications (to appear). Zbl0643.68077MR928772
  7. [NE75] J. NEVEU, Discrete-Parameter Martingale, English Translation, North-Holland, Amsterdam, 1975. Zbl0345.60026MR402915
  8. [SE77] R. SEDGEWICK, The Analysis of Quicksort Programs, Acta Informatica, Vol. 7, 1977, pp. 327-355, and in Quicksort, Garland Pub. Co., New York, 1980. Zbl0325.68016MR451845

Citations in EuDML Documents

top
  1. P. Hennequin, Combinatorial analysis of quicksort algorithm
  2. Uwe Rösler, A limit theorem for “quicksort”
  3. Rudolf Grübel, Anke Reimers, On the number of iterations required by Von Neumann addition
  4. Hosam M. Mahmoud, Reza Modarres, Robert T. Smythe, Analysis of quickselect : an algorithm for order statistics
  5. Michael Cramer, A note concerning the limit distribution of the quicksort algorithm
  6. Rudolf Grübel, Anke Reimers, On the number of iterations required by Von Neumann addition

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.