close
Skip to main content
Springer Nature Link
Log in

Multikey Quickselect

  • Published:
Save article
View saved research
BERJAYA Algorithmica Aims and scope Submit manuscript

Abstract

We present multikey quickselect: an efficient, in-place, easy-to-implement algorithm for the selection problem for strings. We analyze its expected cost under a uniform model, measured as the number of character comparisons and pointer swaps, depending on the alphabet cardinality. From the analysis, we derive a binary variant of the algorithm, which is more efficient when the range of values for the alphabet is known. This variant can also be applied to multikey quicksort.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+
from $39.99 /Month
  • Starting from 10 chapters or articles per month
  • Access and download chapters and articles from more than 300k books and 2,500 journals
  • Cancel anytime
View plans

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
BERJAYA
Fig. 2
BERJAYA
Fig. 3
BERJAYA
Fig. 4
BERJAYA

Similar content being viewed by others

Explore related subjects

Discover the latest articles, books and news in related subjects, suggested using machine learning.

References

  1. Bentley, J.L., McIlroy, M.D.: Engineering a sort function. Softw. Pract. Exp. 23(11), 1249–1265 (1993)

    Article  Google Scholar 

  2. Bentley, J.L., Sedgewick, R.: Fast algorithms for sorting and searching strings. In: SODA’97: Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 360–369. Society for Industrial and Applied Mathematics, Philadelphia (1997)

    Google Scholar 

  3. Clément, J., Flajolet, P., Vallée, B.: Dynamical sources in information theory: a general analysis of trie structures. Algorithmica 29(1), 307–369 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  4. Franceschini, G., Grossi, R.: A general technique for managing strings in comparison-driven data structures. In: Díaz, J., Karhumäki, J., Lepistö, A., Sannella, D. (eds.) ICALP’04: Proceedings of the 31st International Colloquium on Automata, Languages and Programming. Lecture Notes in Computer Science, vol. 3142, pp. 606–617. Springer, Berlin/Heidelberg (2004)

    Chapter  Google Scholar 

  5. Frias, L.: On the number of string lookups in BSTs (and related algorithms) with digital access. Technical report LSI-09-14-R, Universitat Politècnica de Catalunya, Departament de Llenguatges i Sistemes Informàtics (2009). http://www.lsi.upc.edu/dept/techreps/llistat_detallat.php?id=1053

  6. Grossi, R., Italiano, G.F.: Efficient techniques for maintaining multidimensional keys in linked data structures. In: Wiedermann, J., van Emde Boas, P., Nielsen, M. (eds.) Automata, Languages and Programming, 26th International Colloquium, ICALP’99, Prague, Czech Republic, July 11–15, 1999. Lecture Notes in Computer Science, vol. 1644, pp. 372–381. Springer, Berlin/Heidelberg (1999)

    Chapter  Google Scholar 

  7. Hildebrandt, P., Isbitz, H.: Radix exchange—an internal sorting method for digital computers. J. ACM 6(2), 156–163 (1959)

    MATH  MathSciNet  Google Scholar 

  8. International Standard ISO/IEC 14882: Programming Languages—C++, 3rd edn. (2011). American National Standard Institute

    Google Scholar 

  9. Kärkkäinen, J., Rantala, T.: Engineering radix sort for strings. In: Amir, A., Turpin, A., Moffat, A. (eds.) String Processing and Information Retrieval, 15th International Symposium, SPIRE 2008, Melbourne, Australia, November 10–12, 2008. Lecture Notes in Computer Science, vol. 5280, pp. 3–14. Springer, Berlin/Heidelberg (2008)

    Chapter  Google Scholar 

  10. Kim, E., Park, K.: Improving multikey quicksort for sorting strings with many equal elements. Inf. Process. Lett. 109(9), 454–459 (2009)

    Article  MATH  Google Scholar 

  11. Mahmoud, H., Flajolet, P., Jacquet, P., Régnier, M.: Analytic variations on bucket selection and sorting. Acta Inform. 36(9–10), 735–760 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  12. Mahmoud, H.M., Modarres, R., Smythe, R.T.: Analysis of quickselect: an algorithm for order statistics. RAIRO Theor. Inform. Appl. 29(4), 255–276 (1995)

    MATH  MathSciNet  Google Scholar 

  13. Martínez, C., Roura, S.: Optimal sampling strategies in quicksort and quickselect. SIAM J. Comput. 31(3), 683–705 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  14. Mcilroy, P.M., Bostic, K., Mcilroy, M.D.: Engineering radix sort. Comput. Syst. 6, 5–27 (1993)

    Google Scholar 

  15. Roura, S.: Digital access to comparison-based tree data structures and algorithms. J. Algorithms 40(1), 1–23 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  16. Roura, S.: Improved master theorems for divide-and-conquer recurrences. J. ACM 48(2), 170–205 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  17. Sinha, R., Wirth, A.: Engineering burstsort: towards fast in-place string sorting. In: McGeoch, C.C. (ed.) Experimental Algorithms, 7th International Workshop, WEA 2008, Provincetown, MA, USA, May 30–June 1, 2008. Lecture Notes in Computer Science, vol. 5038, pp. 14–27. Springer, Berlin/Heidelberg (2008)

    Chapter  Google Scholar 

  18. Vallée, B., Clément, J., Fill, J.A., Flajolet, P.: The number of symbol comparisons in quicksort and quickselect. In: 36th International Colloquium on Automata, Languages and Programming (ICALP 2009). Lecture Notes in Computer Science, vol. 5555, pp. 750–763. Springer, Berlin/Heidelberg (2009)

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Departament de LSI, Universitat Politècnica de Catalunya, 08028, Barcelona, Catalonia, Spain

    Leonor Frias & Salvador Roura

Authors
  1. Leonor Frias
    View author publications

    Search author on:PubMed Google Scholar

  2. Salvador Roura
    View author publications

    Search author on:PubMed Google Scholar

Corresponding author

Correspondence to Salvador Roura.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Frias, L., Roura, S. Multikey Quickselect. Algorithmica 69, 958–973 (2014). https://doi.org/10.1007/s00453-013-9775-2

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue date:

  • DOI: https://doi.org/10.1007/s00453-013-9775-2

Keywords