Expected time bounds for selection

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Expected time bounds for selection

Full text

Pdf (694 KB)

Source

Communications of the ACM archive
Volume 18 , Issue 3 (March 1975) table of contents

Pages: 165 - 172

Year of Publication: 1975

ISSN:0001-0782

Authors

Robert W. Floyd	Stanford Univ., Stanford, CA
Ronald L. Rivest	Stanford Univ., Stanford, CA

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 21, Downloads (12 Months): 95, Citation Count: 49

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/360680.360691 What is a DOI?

ABSTRACT

A new selection algorithm is presented which is shown to be very efficient on the average, both theoretically and practically. The number of comparisons used to select the ith smallest of n numbers is n + min(i,n-i) + o(n). A lower bound within 9 percent of the above formula is also derived.

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., Flyod, R. W., Pratt, V., Rivest, R., and Tarjan, R. Time bounds for selection JCSS 7(Aug. 197.), 448-461
	2	Robert W. Floyd , Ronald L. Rivest, Algorithm 489: the algorithm SELECT—for finding the ith smallest of n elements [M1], Communications of the ACM, v.18 n.3, p.173, March 1975 [doi>10.1145/360680.360694]
	3	C. A. R. Hoare, Algorithm 63: partition, Communications of the ACM, v.4 n.7, p.321, July 1961 [doi>10.1145/366622.366642]
	4	Knuth, Donald E. Mathematical analysis of algorithms. Computer Sei. Dept. Rep. STAN-CS-71-206. Stantbrd U., Mar. 1971.27 pp.
	5	Lindgren, B.W. Statistical Theory. The MacMillan Co., New York, 1962.
	6	Rivest, Ronald L., and Floyd, Robert W. Bounds on the expected time for median computations (extended abstract). Courant CompLter Science Symposium 9, Randall Rustin {Ed.} Algorithmics Press, New York, 1973, pp. 69-76.
	7	Rodolfo C. Salazar , Subrata K. Sen, Algorithms: Algorithm 333: MINIT algorithm for linear programming, Communications of the ACM, v.11 n.6, p.437-440, June 1968 [doi>10.1145/363347.363394]

CITED BY 49

	Marc Daumas , Paraskevas Evripidou, Parallel Implementations of the Selection Problem: A Case Study, International Journal of Parallel Programming, v.28 n.1, p.103-131, February 2000
	Howard Karloff , Prabhakar Raghavan, Randomized algorithms and pseudorandom numbers, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.310-321, May 02-04, 1988, Chicago, Illinois, United States
	Bruce Weide, A Survey of Analysis Techniques for Discrete Algorithms, ACM Computing Surveys (CSUR), v.9 n.4, p.291-313, Dec. 1977
	Gary A. Hyslop , Edmund A. Lamagna, An application of the method of Buckets to the selection problem, Proceedings of the 1992 ACM/SIGAPP symposium on Applied computing: technological challenges of the 1990's, p.1167-1172, March 1992, Kansas City, Missouri, United States
	Seth Pettie , Vijaya Ramachandran, Minimizing randomness in minimum spanning tree, parallel connectivity, and set maxima algorithms, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.713-722, January 06-08, 2002, San Francisco, California
	Howard J. Karloff , Prabhakar Raghavan, Randomized algorithms and pseudorandom numbers, Journal of the ACM (JACM), v.40 n.3, p.454-476, July 1993
	Takeshi Tokuyama , Jun Nakano, Geometric algorithms for a minimum cost assignment problem, Proceedings of the seventh annual symposium on Computational geometry, p.262-271, June 10-12, 1991, North Conway, New Hampshire, United States
	Dorit Dor , Uri Zwick, Selecting the median, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.28-37, January 22-24, 1995, San Francisco, California, United States
	Chee K. Yap, New upper bounds for selection, Communications of the ACM, v.19 n.9, p.501-508, Sept. 1976
	Jon L. Bentley , Kenneth L. Clarkson , David B. Levine, Fast linear expected-time alogorithms for computing maxima and convex hulls, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.179-187, January 22-24, 1990, San Francisco, California, United States
	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
	Walter Cunto , J. Ian Munro, Average case selection, Journal of the ACM (JACM), v.36 n.2, p.270-279, April 1989
	Jon L. Bentley , Robert Sedgewick, Fast algorithms for sorting and searching strings, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.360-369, January 05-07, 1997, New Orleans, Louisiana, United States
	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
	Nimrod Megiddo, Linear Programming in Linear Time When the Dimension Is Fixed, Journal of the ACM (JACM), v.31 n.1, p.114-127, Jan. 1984
	Rudolf Loeser, Survey on Algorithms 347, 426, and Quicksort, ACM Transactions on Mathematical Software (TOMS), v.2 n.3, p.290-299, Sept. 1976
	Sanguthevar Rajasekaran, Sorting and selection on parallel disk models, Handbook of massive data sets, Kluwer Academic Publishers, Norwell, MA, 2002
	Jon Louis Bentley, K-d trees for semidynamic point sets, Proceedings of the sixth annual symposium on Computational geometry, p.187-197, June 07-09, 1990, Berkley, California, United States
	Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, ACM Computing Surveys (CSUR), v.28 n.1, p.33-37, March 1996
	Theodore Brown, Remark on “Algorithm 489: The Algorithm SELECT—for Finding the ith Smallest of n Elements [M1]”, ACM Transactions on Mathematical Software (TOMS), v.2 n.3, p.301-304, Sept. 1976
	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
	Jop F. Sibeyn, External selection, Journal of Algorithms, v.58 n.2, p.104-117, February 2006
	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
	Conrado Martínez , Daniel Panario , Alfredo Viola, Adaptive sampling for quickselect, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	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
	Ibraheem Al-Furaih , Srinivas Aluru , Sanjay Goil , Sanjay Ranka, Parallel construction of multidimensional binary search trees, Proceedings of the 10th international conference on Supercomputing, p.205-212, May 25-28, 1996, Philadelphia, Pennsylvania, United States
	Venkatesh Raman , Sarnath Ramnath, Improved upper bounds for time-space trade-offs for selection, Nordic Journal of Computing, v.6 n.2, p.162-180, Summer 1999
	Ibraheem Al-furiah , Srinivas Aluru , Sanjay Goil , Sanjay Ranka, Practical Algorithms for Selection on Coarse-Grained Parallel Computers, IEEE Transactions on Parallel and Distributed Systems, v.8 n.8, p.813-824, August 1997
	Bruce W. Schmeiser, The generation of order statistics in digital computer simulation: A survey, Proceedings of the 10th conference on Winter simulation, p.137-140, December 04-06, 1978, Miami Beach, FL
	Jesper Bojesen , Jyrki Katajainen , Maz Spork, Performance engineering case study: heap construction, Journal of Experimental Algorithmics (JEA), 5, p.15-es, 2000
	Sanguthevar Rajasekaran , Sartaj Sahni, Sorting, Selection, and Routing on the Array with Reconfigurable Optical Buses, IEEE Transactions on Parallel and Distributed Systems, v.8 n.11, p.1123-1132, November 1997
	Walter Cunto , J. Ian Munro, Average case selection, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.369-375, December 1984
	Ibraheem Al-Furaih , Srinivas Aluru , Sanjay Goil , Sanjay Ranka, Parallel Construction of Multidimensional Binary Search Trees, IEEE Transactions on Parallel and Distributed Systems, v.11 n.2, p.136-148, February 2000
	Arvind Arasu , Gurmeet Singh Manku, Approximate counts and quantiles over sliding windows, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France
	Prosenjit Bose , Erik D. Demaine , Ferran Hurtado , John Iacono , Stefan Langerman , Pat Morin, Geodesic ham-sandwich cuts, Proceedings of the twentieth annual symposium on Computational geometry, June 08-11, 2004, Brooklyn, New York, USA
	Yana Kortsarts , Jeffrey Rufinus, How (and why) to introduce Monte Carlo randomized algorithms into a basic algorithms course?, Journal of Computing Sciences in Colleges, v.21 n.2, p.195-203, December 2005
	Sanguthevar Rajasekaran , Jaime Davila, Packet routing and selection on the POPS network, Journal of Parallel and Distributed Computing, v.65 n.8, p.927-933, August 2005
	Marc Daumas , Paraskevas Evripidou, Results of Parallel Implementations of the Selection Problem Using Sisal, Proceedings of the IFIP WG10.3. Working Conference on Architectures and Compilation Techniques for Fine and Medium Grain Parallelism, p.265-272, January 20-22, 1993
	Krzysztof C. Kiwiel, On Floyd and Rivest's SELECT algorithm, Theoretical Computer Science, v.347 n.1-2, p.214-238, 30 November 2005
	Markus Hegland, Implementing partition on vector computers, Proceedings of the 5th international conference on Supercomputing, p.304-311, June 17-21, 1991, Cologne, West Germany
	Tien-Ching Lin , D. T. Lee, Randomized algorithm for the sum selection problem, Theoretical Computer Science, v.377 n.1-3, p.151-156, May, 2007
	Seth Pettie , Vijaya Ramachandran, Randomized minimum spanning tree algorithms using exponentially fewer random bits, ACM Transactions on Algorithms (TALG), v.4 n.1, p.1-27, March 2008
	Khaled Alsabti , Sanjay Ranka , Vineet Singh, A One-Pass Algorithm for Accurately Estimating Quantiles for Disk-Resident Data, Proceedings of the 23rd International Conference on Very Large Data Bases, p.346-355, August 25-29, 1997
	Jiexing Li , Yufei Tao , Xiaokui Xiao, Preservation of proximity privacy in publishing numerical sensitive data, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada
	Ka-Ling Fok , Tien-Tsin Wong , Man-Leung Wong, Evolutionary Computing on Consumer Graphics Hardware, IEEE Intelligent Systems, v.22 n.2, p.69-78, March 2007
	Timothy M. Chan, Comparison-based time-space lower bounds for selection, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.140-149, January 04-06, 2009, New York, New York
	Jeffrey Considine , Marios Hadjieleftheriou , Feifei Li , John Byers , George Kollios, Robust approximate aggregation in sensor data management systems, ACM Transactions on Database Systems (TODS), v.34 n.1, p.1-35, April 2009
	Umamaheswari C. Devi , J. H. Anderson, Tardiness bounds under global EDF scheduling on a multiprocessor, Real-Time Systems, v.38 n.2, p.133-189, February 2008