article

Free access

Finding the ith largest of n for small i,n

Authors:

William Gasarch,

William PughAuthors Info & Claims

ACM SIGACT News, Volume 27, Issue 2

Pages 88 - 96

https://doi.org/10.1145/235767.235772

Published: 01 July 1996 Publication History

Abstract

A classic problem in computer science is selection: given a list of n numbers, find the ith largest, using the fewest number of comparisons. We are interested in the exact number of comparisons required for specific small values of i and n. We have written a program that can be used either to find the exact number of comparisons for very low values of i and n, or to find upper bounds on the number of comparisons for slightly larger values of i and n. In some cases we have improved on the results in the literature and have additional improvements contingent on a conjecture.

References

[1]

{1} S. Bent and J. John. Finding the median requires 2n comparisons. In Proc. of the 17th ACM Sym. on Theory of Computing, 1985.

Digital Library

[2]

{2} M. Blum, R. W. Floyd, V. R. Pratt, R. L. Rivest, and R. E. Tarjan. Time bounds for selection. J. Comput. Syat. Sci., 7:448-461, 1973.

Digital Library

[3]

{3} D. Dor. Selection Algorithms. PhD thesis, Tel-Aviv University, 1995.

[4]

{4} D. Dor and U. Zwick. Selecting the median. In Proc. 6th Annual Sym. on Discrete Algorithms, 1995.

Digital Library

[5]

{5} F. Fussenegger and H. Gabow. A counting approach to lower bounds for selection problems. J. ACM, 26(2):227-238, April 1979.

Digital Library

[6]

{6} J. W. John. The Complexity of Selection Problems. PhD thesis, The University of Wisconsin at Madison, 1985.

Digital Library

[7]

{7} J. W. John. A new lower bound for the set-partitioning problem. SIAM J. Comput., 17(4):640- 647, Aug. 1988.

Digital Library

[8]

{8} D. Kirkpatrick. A unified lower bound for selection and set partitioning problems. J. ACM, 39, 1981.

Digital Library

[9]

{9} D. E. Knuth. Sorting and Searching, volume 3 of The Art of Computer Programming. Addison-Wesley, Reading, MA, 1973.

[10]

{10} A. Newell, J. Shaw, and H. Simon. Efficient randomized pattern-matching algorithms. IBM Journal of Res. and Dev., pages 320-355, 1958.

[11]

{11} N. J. Nilsson. Principles of Artificial Intelligence. Morgan Kaufmann Publishers, 1980.

Digital Library

[12]

{12} V. Pratt and F. F. Yao. On lower bounds for computing the i-th largest element. In Proc. of the 14th IEEE Sym. on Found. of Comp. Sci., pages 70-81, 1973.

Digital Library

[13]

{13} Schoenhage, Paterson, and Pippenger. Finding the median. J. Comput. Syst. Sci., 13, 1976.

[14]

{14} C. Shannon. Programming a computer for playing chess. Philosophical Magazine, 41:256-275, 1950.

[15]

{15} T. Spencer, 1992. Personal communication.

[16]

{16} U. Zwick, February 1996. Personal communication.

Cited By

Chen KDumitrescu A(2020)Selection Algorithms with Small GroupsInternational Journal of Foundations of Computer Science10.1142/S012905412050013631:03(355-369)Online publication date: 1-May-2020
https://doi.org/10.1142/S0129054120500136
Dumitrescu A(2019)A Selectable Sloppy HeapAlgorithms10.3390/a1203005812:3(58)Online publication date: 6-Mar-2019
https://doi.org/10.3390/a12030058
Hofri M(2013)Optimal selection and sorting via dynamic programmingJournal of Experimental Algorithmics (JEA)10.1145/2444016.249337318(2.1-2.14)Online publication date: 15-Aug-2013
https://dl.acm.org/doi/10.1145/2444016.2493373
Show More Cited By

Index Terms

Finding the ith largest of n for small i,n
1. Mathematics of computing
  1. Mathematical analysis
    1. Numerical analysis
      1. Number-theoretic computations
  2. Mathematical software
2. Theory of computation
  1. Design and analysis of algorithms
    1. Data structures design and analysis
      1. Sorting and searching

Recommendations

Algorithm 489: the algorithm SELECT—for finding the ith smallest of n elements [M1]

SELECT will rearrange the values of array segment X[L: R] so that X[K] (for some given K; L ≤ K ≤ R) will contain the (K-L+1)-th smallest value, L ≤ I ≤ K will imply X[I] ≤ X[K], and K ≤ I ≤ R will imply X[I] ≥ X[K. While SELECT is thus functionally ...
Length thresholds for graphic lists given fixed largest and smallest entries and bounded gaps

In a list (d"1,...,d"n) of positive integers, let r and s denote the largest and smallest entries. A list is gap-free if each integer between r and s is present. We prove that a gap-free list with even sum is graphic if it has at least r+r+s+12s terms. ...
The largest singletons of set partitions

Recently, Deutsch and Elizalde have studied the largest and the smallest fixed points of permutations. Motivated by their work, we consider the analogous problems in set partitions. Let A"n","k denote the number of partitions of {1,2,...,n+1} with the ...

Comments

Information & Contributors

Information

Published In

cover image ACM SIGACT News

ACM SIGACT News Volume 27, Issue 2

June 1996

51 pages

ISSN:0163-5700

DOI:10.1145/235767

Editor:
Ian Parberry
Univ. of North Texas, Denton

Issue’s Table of Contents

Copyright © 1996 Authors.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 1996

Published in SIGACT Volume 27, Issue 2

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
424
Total Downloads

Downloads (Last 12 months)66
Downloads (Last 6 weeks)3

Reflects downloads up to 30 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Chen KDumitrescu A(2020)Selection Algorithms with Small GroupsInternational Journal of Foundations of Computer Science10.1142/S012905412050013631:03(355-369)Online publication date: 1-May-2020
https://doi.org/10.1142/S0129054120500136
Dumitrescu A(2019)A Selectable Sloppy HeapAlgorithms10.3390/a1203005812:3(58)Online publication date: 6-Mar-2019
https://doi.org/10.3390/a12030058
Hofri M(2013)Optimal selection and sorting via dynamic programmingJournal of Experimental Algorithmics (JEA)10.1145/2444016.249337318(2.1-2.14)Online publication date: 15-Aug-2013
https://dl.acm.org/doi/10.1145/2444016.2493373
Eusterbrock J(2005)Program synthesis from examples by theory formationFoundations of Intelligent Systems10.1007/3-540-63614-5_36(370-380)Online publication date: 25-Jul-2005
https://doi.org/10.1007/3-540-63614-5_36

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents