Multikey Quickselect

Springer Science and Business Media LLC - Tập 69 Số 4 - Trang 958-973 - 2014
Frias, Leonor1, Roura, Salvador1
1Departament de LSI, Universitat Politècnica de Catalunya, Barcelona, Spain

Tóm tắt

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.

Tài liệu tham khảo

citation_journal_title=Softw. Pract. Exp.; citation_title=Engineering a sort function; citation_author=J.L. Bentley, M.D. McIlroy; citation_volume=23; citation_issue=11; citation_publication_date=1993; citation_pages=1249-1265; citation_doi=10.1002/spe.4380231105; citation_id=CR1 citation_title=Fast algorithms for sorting and searching strings; citation_inbook_title=SODA’97: Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms; citation_publication_date=1997; citation_pages=360-369; citation_id=CR2; citation_author=J.L. Bentley; citation_author=R. Sedgewick; citation_publisher=Society for Industrial and Applied Mathematics citation_journal_title=Algorithmica; citation_title=Dynamical sources in information theory: a general analysis of trie structures; citation_author=J. Clément, P. Flajolet, B. Vallée; citation_volume=29; citation_issue=1; citation_publication_date=2001; citation_pages=307-369; citation_doi=10.1007/BF02679623; citation_id=CR3 citation_title=A general technique for managing strings in comparison-driven data structures; citation_inbook_title=ICALP’04: Proceedings of the 31st International Colloquium on Automata, Languages and Programming; citation_publication_date=2004; citation_pages=606-617; citation_id=CR4; citation_author=G. Franceschini; citation_author=R. Grossi; citation_publisher=Springer 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 citation_title=Efficient techniques for maintaining multidimensional keys in linked data structures; citation_inbook_title=Automata, Languages and Programming, 26th International Colloquium; citation_publication_date=1999; citation_pages=372-381; citation_id=CR6; citation_author=R. Grossi; citation_author=G.F. Italiano; citation_publisher=Springer citation_journal_title=J. ACM; citation_title=Radix exchange—an internal sorting method for digital computers; citation_author=P. Hildebrandt, H. Isbitz; citation_volume=6; citation_issue=2; citation_publication_date=1959; citation_pages=156-163; citation_id=CR7 citation_title=Programming Languages—C++; citation_publication_date=2011; citation_id=CR8 citation_title=Engineering radix sort for strings; citation_inbook_title=String Processing and Information Retrieval, 15th International Symposium; citation_publication_date=2008; citation_pages=3-14; citation_id=CR9; citation_author=J. Kärkkäinen; citation_author=T. Rantala; citation_publisher=Springer citation_journal_title=Inf. Process. Lett.; citation_title=Improving multikey quicksort for sorting strings with many equal elements; citation_author=E. Kim, K. Park; citation_volume=109; citation_issue=9; citation_publication_date=2009; citation_pages=454-459; citation_doi=10.1016/j.ipl.2009.01.007; citation_id=CR10 citation_journal_title=Acta Inform.; citation_title=Analytic variations on bucket selection and sorting; citation_author=H. Mahmoud, P. Flajolet, P. Jacquet, M. Régnier; citation_volume=36; citation_issue=9–10; citation_publication_date=2000; citation_pages=735-760; citation_doi=10.1007/s002360050173; citation_id=CR11 citation_journal_title=RAIRO Theor. Inform. Appl.; citation_title=Analysis of quickselect: an algorithm for order statistics; citation_author=H.M. Mahmoud, R. Modarres, R.T. Smythe; citation_volume=29; citation_issue=4; citation_publication_date=1995; citation_pages=255-276; citation_id=CR12 citation_journal_title=SIAM J. Comput.; citation_title=Optimal sampling strategies in quicksort and quickselect; citation_author=C. Martínez, S. Roura; citation_volume=31; citation_issue=3; citation_publication_date=2001; citation_pages=683-705; citation_doi=10.1137/S0097539700382108; citation_id=CR13 citation_journal_title=Comput. Syst.; citation_title=Engineering radix sort; citation_author=P.M. Mcilroy, K. Bostic, M.D. Mcilroy; citation_volume=6; citation_publication_date=1993; citation_pages=5-27; citation_id=CR14 citation_journal_title=J. Algorithms; citation_title=Digital access to comparison-based tree data structures and algorithms; citation_author=S. Roura; citation_volume=40; citation_issue=1; citation_publication_date=2001; citation_pages=1-23; citation_doi=10.1006/jagm.2001.1160; citation_id=CR15 citation_journal_title=J. ACM; citation_title=Improved master theorems for divide-and-conquer recurrences; citation_author=S. Roura; citation_volume=48; citation_issue=2; citation_publication_date=2001; citation_pages=170-205; citation_doi=10.1145/375827.375837; citation_id=CR16 citation_title=Engineering burstsort: towards fast in-place string sorting; citation_inbook_title=Experimental Algorithms, 7th International Workshop; citation_publication_date=2008; citation_pages=14-27; citation_id=CR17; citation_author=R. Sinha; citation_author=A. Wirth; citation_publisher=Springer citation_title=The number of symbol comparisons in quicksort and quickselect; citation_inbook_title=36th International Colloquium on Automata, Languages and Programming (ICALP 2009); citation_publication_date=2009; citation_pages=750-763; citation_id=CR18; citation_author=B. Vallée; citation_author=J. Clément; citation_author=J.A. Fill; citation_author=P. Flajolet; citation_publisher=Springer