AbstractWe consider the problem of finding an element of a given rank in a totally ordered set given in a read-only array, using limited extra storage cells. We give new algorithms for various ranges of extra space. Our upper bounds improve the previously known bounds in the range of space s such that s is o(\lg^2 n) and s >= (1+e) lg lg n / lg lg lg n for any positive constant e < 1. We also give faster rank sensitive algorithms. These algorithms are quite efficient for finding small ranks and their runtime match the upper bound of the best known algorithms when median element is to be found.
Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems
Additional Key Words and Phrases: selection, read-only memory, limited storage algorithms
Selected references
- Manuel Blum, Robert W. Floyd, Vaughan Pratt, Ronald L. Rivest, and Robert E. Tarjan. Time bounds for selection. Journal of Computer and System Sciences, 7(4):448-461, August 1973.
- Dorit Dor and Uri Zwick. Selecting the median. In Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 28-37, San Francisco, California, 22-24 January 1995.
- Greg N. Frederickson. Upper bounds for time-space trade-offs in sorting and selection. Journal of Computer and System Sciences, 34(1):19-26, February 1987.
- J. I. Munro and M. S. Paterson. Selection and sorting with limited storage. Theoretical Computer Science, 12(3):315-323, November 1980.
- J. Ian Munro and Venkatesh Raman. Selection from read-only memory and sorting with minimum data movement. Theoretical Computer Science, 165(2):311-323, 10 October 1996.
- A. Schönhage, M. Paterson, and N. Pippenger. Finding the median. Journal of Computer and System Sciences, 13(2):184-199, October 1976.