Multikey Quickselect
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