×

Asymptotic analysis of (3,2,1)-shell sort. (English) Zbl 1037.68049

Summary: We analyze the \((3,2,1)\)-Shell Sort algorithm under the usual random permutation model.

MSC:

68P10 Searching and sorting
PDF BibTeX XML Cite
Full Text: DOI Link

References:

[1] and Normal approximation and asymptotic expansions, Wiley, New York, 1976. · Zbl 0331.41023
[2] Probability and measure (2nd edition), Wiley, New York, 1986.
[3] Markov chains (2nd edition), Springer-Verlag, New York, 1967.
[4] Introduction to stochastic processes, Prentice-Hall, Englewood Cliffs, NJ, 1975. · Zbl 0341.60019
[5] Janson, Random Struct Alg 10 pp 125– (1997)
[6] The art of computer programming 3: Sorting and searching, Addison-Wesley, Reading, MA, 1973. · Zbl 0302.68010
[7] Kolmogorov, Select Transl Math Stat Probab 2 pp 109– (1962)
[8] Lent, Ann Appl Probab 6 pp 1284– (1996)
[9] Louchard, BIT 26 pp 17– (1986)
[10] Sorting: A distribution theory, Wiley, New York, 2000. · Zbl 0985.68015
[11] Meizler, Dokl Akad Nauk SSSR 60 pp 1127– (1948)
[12] Pyke, J Roy Stat Soc Ser B 7 pp 395– (1965)
[13] Stochastic processes, Wiley, New York, 1983.
[14] Analysis of Shellsort and related algorithms, Algorithms?ESA ’96: Fourth Annu Eur Symp Alg, Barcelona, Spain, September 25-27, 1996, (Editors), Springer-Verlag, Berlin, New York, pp. 1-11.
[15] and An introduction to the analysis of algorithms, Addison-Wesley, Reading, MA, 1996.
[16] Shell, Commun ACM 2 pp 30– (1959)
[17] Smythe, Algorithmica 31 pp 442– (2001)
[18] Steck, Univ Calif Publ Stat 2 pp 235– (1957)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.