ACM Portal
  Subscribe (Full Service)    Register (Limited Service, Free)    Login
  Search:   The ACM Digital Library   The Guide
  
ACM Home Page
Please provide us with feedback. Feedback
A sorting problem and its complexity
Full text PdfPdf (195 KB)
Source
Communications of the ACM archive
Volume 15 ,  Issue 6  (June 1972) table of contents
Pages: 462 - 464  
Year of Publication: 1972
ISSN:0001-0782
Author
Ira Pohl  Univ. of California, Santa Cruz, Santa Cruz
Publisher
ACM  New York, NY, USA
Bibliometrics
Downloads (6 Weeks): n/a,   Downloads (12 Months): n/a,   Citation Count: 7
Additional Information:

abstract   references   cited by   index terms   collaborative colleagues  

Tools and Actions: Request Permissions Request Permissions    Review this Article  
DOI Bookmark: Use this link to bookmark this Article: http://doi.acm.org/10.1145/361405.361423
What is a DOI?

ABSTRACT

A technique for proving min-max norms of sorting algorithms is given. One new algorithm for finding the minimum and maximum elements of a set with fewest comparisons is proved optimal with this technique.


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
Hadian, A., and Sobel, M. Selecting the tth largest using binary errorless comparisons. TR No. 121, U. of Minnesota, Department of Statistics, May 1969.
 
2
Pohl, I. Heuristic search viewed as path finding in a graph. J. Artif. bltell. 1 (1970), 193-204.
 
3
Pohl, I. A minimum storage algorithm for computing the median. IBM Tech. Rep. RC 2701, Nov. 1969.
 
4
Pohl, I. Syntactic models of cognitive behavior. 1CS Dep. Rep., U. of California, Santa Cruz. Presented at the NATO Symposium on Human Thinking, St. Maximin, France, Aug. 1971.

CITED BY  7
C. K. Yap, Space-time tradeoffs and first order problems in a model of programs, Proceedings of the twelfth annual ACM symposium on Theory of computing, p.318-325, April 28-30, 1980, Los Angeles, California, 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
Walter Cunto , J. Ian Munro, Average case selection, Journal of the ACM (JACM), v.36 n.2, p.270-279, April 1989
Narayan Murthy, Min-max sort: a simple sorting method (abstract only), Proceedings of the 15th annual conference on Computer Science, p.365, February 1987, St. Louis, Missouri, United States
Frank Fussenegger , Harold N. Gabow, A Counting Approach to Lower Bounds for Selection Problems, Journal of the ACM (JACM), v.26 n.2, p.227-238, April 1979
Hsien-Kuei Hwang , Tsung-Hsi Tsai, An asymptotic theory for recurrence relations based on minimization and maximization, Theoretical Computer Science, v.290 n.3, p.1475-1501, 3 January 2003
Walter Cunto , J. Ian Munro, Average case selection, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.369-375, December 1984

INDEX TERMS

Keywords:
computational combinatorics, computational complexity, sorting

Collaborative Colleagues:
Ira Pohl: colleagues

The ACM Portal is published by the Association for Computing Machinery. Copyright © 2009 ACM, Inc.
Terms of Usage   Privacy Policy   Code of Ethics   Contact Us

Useful downloads: Adobe Acrobat    QuickTime    Windows Media Player    Real Player