Abstract
By developing and exploiting new in-place techniques, we show that finding the element with the median value out of n elements stored in an array can be performed in-place in (2.95+∈)n (for any ∈>0) comparisons and in linear time. This is arbitrarily close to the upper bound for the same problem without space-restrictions.
To make the algorithm competitive we also try to minimize the number of element moves performed by the algorithm since this is the other critical operation. This has resulted in a trade-off between the number of comparisons and the number of moves. By minimizing the sum of the critical operations we achieve an algorithm that uses at most 3.75n comparisons and 9n moves for finding the median in-place. This is, in principle, twice as good as earlier attempts on implicit selection for both of the operations.
Preview
Unable to display preview. Download preview PDF.
References
S. W. Bent, J. W. John, Finding the median requires 2n comparisons, In Proceedings of the 17th Annual Symposium on Theory of Computing, pp. 213–216, 1985.
M. Blum, R. W. Floyd, V. Pratt, R. L. Rivest, and R. E. Tarjan, Time bounds for selection, Journal of Computer and System Sciences, 7:448–461, 1973.
S. Carlsson and M. Sundström, Linear-time In-place Selection in Less than 3n Comparisons, extended version available at 〈URL:http://www. sm. luth. se/∼msm/reports/in-place.ps〉
S. Carlsson, The Deap — A double-ended heap to implement double-ended priority queues, Information processing Letters 26 (1):33–36, 1987.
D. Dor and U. Zwick, Selecting the median, In Proceedings of the 6th ACM-SIAM Symposium on Discrete Algorithms (SODA'95), San Francisco, California, January 1995.
T. W. Lai and D. Wood, Implicit Selection, In SWAT 88, pp. 14–23, 1988.
A. Schönhage, M. Paterson, and N. Pippenger, Finding the median, Journal of Computer and System Sciences, 13:184–199, 1976.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1995 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Carlsson, S., Sundström, M. (1995). Linear-time in-place selection in less than 3n comparisons. In: Staples, J., Eades, P., Katoh, N., Moffat, A. (eds) Algorithms and Computations. ISAAC 1995. Lecture Notes in Computer Science, vol 1004. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0015429
Download citation
DOI: https://doi.org/10.1007/BFb0015429
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-60573-7
Online ISBN: 978-3-540-47766-2
eBook Packages: Springer Book Archive