Average case selection

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Average case selection

Full text

Pdf (532 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the sixteenth annual ACM symposium on Theory of computing table of contents

Pages: 369 - 375

Year of Publication: 1984

ISBN:0-89791-133-4

Authors

Walter Cunto
J. Ian Munro

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 18, Citation Count: 5

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/800057.808702 What is a DOI?

ABSTRACT

We consider problems such as selecting the k-th smallest of n numbers in as few comparisons as possible on average. n + k - 0(1) comparisons are proved to be necessary for this particular problem when k ≤ n/2. This shows a technique of Floyd and Rivest is essentially optimal. 7n/4 &equil; o(n) comparisons, on average, are shown to be necessary and sufficient to find the maximum and median of a set. An upper bound of 9n/4 + o(n) and a lower bound of 2n − o(n) are shown for the max-min-median problem.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Blum, M., Floyd,.R., Pratt, V., Rivest, R., and Tarjan, R., Time Bounds for Selection, JCSS 7, 448-461 (1973).
	2	Dobkin, D.P., Eisenstat, S., Lipton, R.J., Munro, J.I., and Snyder, L., The Complexity of a Problem in Epidemiology, unpublished manuscript (1976).
	3	Robert W. Floyd , Ronald L. Rivest, Expected time bounds for selection, Communications of the ACM, v.18 n.3, p.165-172, March 1975 [doi>10.1145/360680.360691]
	4	C. A. R. Hoare, Algorithm 65: find, Communications of the ACM, v.4 n.7, p.321-322, July 1961 [doi>10.1145/366622.366647]
	5	Ira Pohl, A sorting problem and its complexity, Communications of the ACM, v.15 n.6, p.462-464, June 1972 [doi>10.1145/361405.361423]
	6	Pohl, I., Minimean Optimality in Sorting Algorithms, 16th IEEE SWAT, 71-74 (1975).
	7	J. T. Postmus , A. H.G. Rinnooy Kan , G. T. Timmer, An efficient dynamic selection method, Communications of the ACM, v.26 n.11, p.878-881, Nov. 1983 [doi>10.1145/182.358440]

CITED BY 5

	Dan E. Willard, Optimal sample cost residues for differential database batch query problems, Journal of the ACM (JACM), v.38 n.1, p.104-119, Jan. 1991
	S W Bent , J W John, Finding the median requires 2n comparisons, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.213-216, May 06-08, 1985, Providence, Rhode Island, United States
	Alexandros V. Gerbessiotis , Constantinos J. Siniolakis, Deterministic sorting and randomized median finding on the BSP model, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.223-232, June 24-26, 1996, Padua, Italy
	Alexandros V. Gerbessiotis , Constantinos J. Siniolakis, Architecture independent parallel selection with applications to parallel priority queues, Theoretical Computer Science, v.301 n.1-3, p.119-142, 14 May 2003
	Alexandros V. Gerbessiotis , Constantinos J. Siniolakis, Randomized selection in n + C + o(n) comparisons, Information Processing Letters, v.88 n.3, p.95-100, 15 November 2003