Abstract
We present an efficient algorithm for the approximate median selection problem. The algorithm works in-place; it is fast and easy to implement. For a large array it returns, with high probability, a very close estimate of the true median. The running time is linear in the length n of the input. The algorithm performs fewer than \( \frac{4} {3}n \) comparisons and \( \frac{1} {3}n \) exchanges on the average. We present analytical results of the performance of the algorithm, as well as experimental illustrations of its precision.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
A.V. Aho, J.E. Hopcroft, and J.D. Ullman. The Design and Analysis of Computeralgorithms. Addison Wesley, Reading, MA 1974.
G. Brassard and P. Bratley. Fundamentals of Algorithmics. Prentice-Hall, Englewood Cliffs, NJ 1996.
S. Battiato, D. Cantone, D. Catalano, G. Cincotti, and M. Hofri. An Efficient Algorithm for the Approximate Median Selection Problem. Technical Report WPICS-TR-99-26, Worcester Polytechnic Institute, October 1999. Available from http:/ftp://ftp.cs.wpi.edu/pub/techreports/99-26.ps.gz.
M. Blum, R.W. Floyd, V. Pratt, R.L. Rivest, and R. Tarjan. Time bounds for selection. Journal of Computer and Systems Sciences, 7(4):448–461, 1973.
S. Carlsson, M. Sundstrom. Linear-time In-place Selection in Less than 3n Comparisons-Division of Computer Science, Lulea University of Technology, S-971 87 LULEA, Sweden.
T.H. Cormen, C.E. Leiserson, and R.L. Rivest. Introduction to Algorithms. McGraw-Hill, 1990.
W. Cunto and J.I. Munro. Average case selection. Journal of the ACM, 36(2):270–279, 1989.
Alvin W. Drake. Fundamentals of Applied Probability Theory. McGraw-Hill, 1967.
D. Dor, and U. Zwick. Selecting the Median. SIAM Jour. Comp., 28(5):1722–1758, 1999.
G.N. Frederickson, D.B. Johnson. Generalized Selection and Ranking. Proceedings STOC-SIGACT, Los Angeles CA, 12:420–428, 1980.
G.N. Frederickson. The Information Theory Bound is Tight for selection in a heap. Proceedings STOC-SIGACT, Baltimore MD, 22:26–33, 1990.
R.W. Floyd, R.L. Rivest. Expected time bounds for selection. Communications of the ACM, 18(3):165–172, 1975.
C.A.R. Hoare. Algorithm 63(partition) and algorithm 65(find). Communications of the ACM, 4(7):321–322, 1961.
M. Hofri, Analysis of Algorithms: Computational Methods & Mathematical Tools, Oxford University Press, New York (1995).
C. Hurley and Reza Modarres: Low-Storage quantile estimation, Computational Statistics, 10:311–325, 1995.
P. Kirschenhofer, C. Martinez, and H. Prodinger. Analysis of Hoare’s Find algorithm with median-of-three partition. Random Structures and Algorithms, 10:143–156, 1997.
J. Katajainen. The Ultimate Heapsort, DIKU Report 96/42, Department of Computer Science, Univ. of Copenhagen, 1996.
D.E. Knuth. The Art of Computer Programming, volume 3: Sorting and Searching. Addison-Wesley, 2nd Ed. 1999.
T.W. Lai, and D. Wood. Implicit Selection. Scandinavian Workshop on Algorithm Theory(SWAT88):18–23, LNCS 38Springer-Verlag, 1988.
K. Mehlhorn. Sorting and Searching, Data Structures and Algorithms, volume 1. Springer-Verlag, 1984.
A. Nozaky. Two Entropies of a Generalized Sorting Problems. Journal of Computer and Systems Sciences, 7(5):615–621, 1973.
S. K. Park and K. W. Miller. Random number generators: good ones are hard to find. Communications of the ACM, 31(10):1192–1201, 1988. Updated in Communications of the ACM, 36(7):108-110, 1993.
L. Rosaz. Improving Katajainen’s Ultimate Heapsort, Technical Report N.1115, Laboratoire de Recherche en Informatique, Universit'e de Paris Sud, Orsay, 1997.
P.J. Rousseeuw and G.W. Bassett: The remedian: A robust averaging method for large data sets. Jour. Amer. Statist. Assoc, 409:97–104, 1990.
Savante Janson-Private communication, June 1999.
A. Schonhage, M. Paterson, and N. Pippenger. Finding the median. Journal of Computer and Systems Sciences, 13:184–199, 1976.
B. W. Weide. Space efficient on-line selection algorithm. Proceedings of the 11th symposium of Computer Science and Statistics, on the interface, 308–311. (1978).
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Battiato, S., Cantone, D., Catalano, D., Cincotti, G., Hofri, M. (2000). An Efficient Algorithm for the Approximate Median Selection Problem. In: Bongiovanni, G., Petreschi, R., Gambosi, G. (eds) Algorithms and Complexity. CIAC 2000. Lecture Notes in Computer Science, vol 1767. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-46521-9_19
Download citation
DOI: https://doi.org/10.1007/3-540-46521-9_19
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-67159-6
Online ISBN: 978-3-540-46521-8
eBook Packages: Springer Book Archive