Abstract
We revisit the selection problem, namely that of computing the ith order statistic of n given elements, in particular the classical deterministic algorithm by grouping and partition due to Blum, Floyd, Pratt, Rivest, and Tarjan (1973). While the original algorithm uses groups of odd size at least 5 and runs in linear time, it has been perpetuated in the literature that using groups of 3 or 4 will force the worst-case running time to become superlinear, namely \(\Omega (n \log {n})\). We first point out that the arguments existent in the literature justifying the superlinear worst-case running time fall short of proving this claim. We further prove that it is possible to use group size 3 or 4 while maintaining the worst case linear running time. To this end we introduce two simple variants of the classical algorithm, the repeated step algorithm and the shifting target algorithm, both running in linear time.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Aho, A.V., Hopcroft, J.E., Ullman, J.D.: Data Structures and Algorithms. Addison-Wesley, Reading (1983)
Ajtai, M., Komlós, J., Steiger, W.L., Szemerédi, E.: Optimal parallel selection has complexity \(O(\log \log {n})\). Journal of Computer and System Sciences 38(1), 125–133 (1989)
Baase, S.: Computer Algorithms: Introduction to Design and Analysis, 2nd edn. Addison-Wesley, Reading (1988)
Battiato, S., Cantone, D., Catalano, D., Cincotti, G., Hofri, M.: An efficient algorithm for the approximate median selection problem. In: Bongiovanni, G., Petreschi, R., Gambosi, G. (eds.) CIAC 2000. LNCS, vol. 1767, p. 226. Springer, Heidelberg (2000)
Bent, S.W., John, J.W.: Finding the median requires \(2n\) comparisons. In: Proceedings of the 17th Annual ACM Symposium on Theory of Computing (STOC 1985), pp. 213–216. ACM (1985)
Blum, M., Floyd, R.W., Pratt, V., Rivest, R.L., Tarjan, R.E.: Time bounds for selection. Journal of Computer and System Sciences 7(4), 448–461 (1973)
Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. MIT Press, Cambridge (2009)
Cormen, T.H., Lee, C., Lin, E.: Instructor’s Manual, to accompany Introduction to Algorithms, 3rd edn. MIT Press, Cambridge (2009)
Cunto, W., Munro, J.I.: Average case selection. Journal of ACM 36(2), 270–279 (1989)
Dasgupta, S., Papadimitriou, C., Vazirani, U.: Algorithms. Mc Graw Hill, New York (2008)
Dor, D., Håstad, J., Ulfberg, S., Zwick, U.: On lower bounds for selecting the median. SIAM Journal on Discrete Mathematics 14(3), 299–311 (2001)
Dor, D., Zwick, U.: Finding the \(\alpha n\)th largest element. Combinatorica 16(1), 41–58 (1996)
Dor, D., Zwick, U.: Selecting the median. SIAM Journal on Computing 28(5), 1722–1758 (1999)
Floyd, R.W., Rivest, R.L.: Expected time bounds for selection. Communications of ACM 18(3), 165–172 (1975)
Fussenegger, F., Gabow, H.N.: A counting approach to lower bounds for selection problems. Journal of ACM 26(2), 227–238 (1979)
Hadian, A., Sobel, M.: Selecting the \(t\)-th largest using binary errorless comparisons. Combinatorial Theory and Its Applications 4, 585–599 (1969)
Hoare, C.A.R.: Algorithm 63 (PARTITION) and algorithm 65 (FIND). Communications of the ACM 4(7), 321–322 (1961)
Hyafil, L.: Bounds for selection. SIAM Journal on Computing 5(1), 109–114 (1976)
John, J.W.: A new lower bound for the set-partitioning problem. SIAM Journal on Computing 17(4), 640–647 (1988)
Kirkpatrick, D.G.: A unified lower bound for selection and set partitioning problems. Journal of ACM 28(1), 150–165 (1981)
Kirkpatrick, D.: Closing a long-standing complexity gap for selection: \(V_{3}\)(42) = 50. In: Brodnik, A., López-Ortiz, A., Raman, V., Viola, A. (eds.) Ianfest-66. LNCS, vol. 8066, pp. 61–76. Springer, Heidelberg (2013)
Kleinberg, J., Tardos, É.: Algorithm Design. Pearson & Addison-Wesley, Boston (2006)
Knuth, D.E.: The Art of Computer Programming. Sorting and Searching, vol. 3, 2nd edn. Addison-Wesley, Reading (1998)
Megiddo, N.: Partitioning with two lines in the plane. Journal of Algorithms 6(3), 430–433 (1985)
Mitzenmacher, M., Upfal, E.: Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press (2005)
Paterson, M.: Progress in selection. In: Karlsson, R., Lingas, A. (eds.) SWAT 1996. LNCS, vol. 1097, pp. 368–379. Springer, Heidelberg (1996)
Schönhage, A., Paterson, M., Pippenger, N.: Finding the median. Journal of Computer and System Sciences 13(2), 184–199 (1976)
Yao, A., Yao, F.: On the average-case complexity of selecting the \(k\)th best. SIAM Journal on Computing 11(3), 428–447 (1982)
Yap, C.K.: New upper bounds for selection. Communications of the ACM 19(9), 501–508 (1976)
Zwick, U.: Personal communication, September 2014
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Chen, K., Dumitrescu, A. (2015). Select with Groups of 3 or 4. In: Dehne, F., Sack, JR., Stege, U. (eds) Algorithms and Data Structures. WADS 2015. Lecture Notes in Computer Science(), vol 9214. Springer, Cham. https://doi.org/10.1007/978-3-319-21840-3_16
Download citation
DOI: https://doi.org/10.1007/978-3-319-21840-3_16
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-21839-7
Online ISBN: 978-3-319-21840-3
eBook Packages: Computer ScienceComputer Science (R0)