×

zbMATH — the first resource for mathematics

The analysis of Quicksort programs. (English) Zbl 0325.68016

MSC:
68W99 Algorithms in computer science
68N01 General topics in the theory of software
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Abramowitz, M., Stegun, I. A.: Handbook of mathematical functions. New York: Dover Publications 1970 · Zbl 0171.38503
[2] Aho, A. V., Hopcroft, J. E., Ullman, J. D.: The design and analysis of computer algorithms. Reading (Mass.): Addison-Wesley 1974 · Zbl 0326.68005
[3] Boothroyd, J.: Sort of a section of the elements of an array by determining the rank of each element (Algorithm 25); Ordering the subscripts of an array section according to the magnitudes of the elements (Algorithm 26). Computer J. 10, pp308-310. [See also notes by R. S. Scowen in Computer J. 12, 408-409 (1969) and by A. D. Woodall in Computer J. 13 (1970)]
[4] Brawn, B. S., Gustavson, F. G., Mankin, E.: Sorting in a paging environment. Comm. ACM 13, 483-494 (1970) · Zbl 0205.19201 · doi:10.1145/362705.362710
[5] Cocke, J., Schwartz, J. T.: Programming languages and their compilers. Preliminary notes. Courant Inst, of Math. Sciences, New York University (1970) · Zbl 0245.68003
[6] Frazer, W. D., McKellar, A. C.: Samplesort: a sampling approach to minimal storage tree sorting. J. ACM 17, 496-507 (1970) · Zbl 0205.19202 · doi:10.1145/321592.321600
[7] Hoare, C. A. R.: Partition (Algorithm 63); Quicksort (Algorithm 64); Find (Algorithm 65). Comm. ACM 4, 321-322 (1961). [See also certification by J. S. Hillmore in Comm. ACM 5, 439 (1962) and by B. Randell and L. J. Russell in Comm. ACM 6, 446 (1963)] · doi:10.1145/366622.366644
[8] Hoare, C. A. R.: Quicksort. Computer J. 5, 10-15 (1962) · Zbl 0108.13601 · doi:10.1093/comjnl/5.1.10
[9] Knuth, D. E.: The art of computer programming 1: Fundamental algorithms. Reading (Mass.): Addison-Wesley 1968 · Zbl 0191.17903
[10] Knuth, D. E.: The art of computer programming 2: Seminumerical algorithms. Reading (Mass.): Addison-Wesley 1969 · Zbl 0191.18001
[11] Knuth, D. E.: The art of computer programming 3: Sorting and searching. Reading (Mass.): Addison-Wesley 1972 · Zbl 0302.68010
[12] Knuth, D. E.: Structured programming with go to statements. Computing Surveys 6, 261-301 (1974) · Zbl 0301.68014 · doi:10.1145/356635.356640
[13] Loeser, R.: Some performance tests of ?quicksort? and descendants. Comm. ACM 17, 143-152 (1974) · doi:10.1145/360860.360870
[14] Morris, R.: Some theorems on sorting. SIAM J. Appl. Math. 17, 1-6 (1969) · Zbl 0169.49101 · doi:10.1137/0117001
[15] Rich, R. P.: Internal sorting methods illustrated with PL/I programs. Englewood Cliffs (N.J.): Prentice-Hall 1972
[16] Scowen, R. S.: Quickersort (Algorithm 271). Comm. ACM 8, 669-670 (1965). (See also certification by C. R. Blair in Comm. ACM 9, 354 (1966)) · doi:10.1145/365660.365678
[17] Sedgewick, R.: Quicksort. Stanford University, Stanford Computer Science Report STAN-CS-75-492, Ph. D. Thesis, May 1975
[18] Sedgewick, R.: Quicksort with equal keys. SIAM J. Computing (to appear) · Zbl 0356.68053
[19] Sedgewick, R.: Implementing Quicksort programs (to appear) · Zbl 0386.68058
[20] Singleton, R. C.: An efficient algorithm for sorting with minimal storage (Algorithm 347). Comm. ACM 12, 185-187 (1969). [See also remarks by R. Griffin and K. A. Redish in Comm. ACM 13, 54 (1970) and by R. Peto in Comm. ACM 13, 624 (1970)] · doi:10.1145/362875.362901
[21] van Emden, M. N.: Increasing the efficiency of quicksort (Algorithm 402). Comm. ACM 13, 693-694 (1970). [See also the article by the same name in Comm. ACM 13, 563-567 (1970)] · Zbl 0198.50703
[22] Wirth, N.: Algorithms + Data Structures = Programs. Englewood Cliffs (N. J.): Prentice-Hall 1976 · Zbl 0375.68005
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.