Article

Free access

Fast algorithms for sorting and searching strings

Authors:

Jon L. Bentley,

Robert SedgewickAuthors Info & Claims

SODA '97: Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms

Pages 360 - 369

Published: 05 January 1997 Publication History

PDF eReader

References

[1]

Appel, A.W. and Jacobson, G.J. The World's Fastest Scrabble Program. Communications of the ACM 31, 5 (May 1988), 572-578.

Digital Library

Google Scholar

[2]

Bentley, J.L. and McIlroy, M.D. Engineering A Sort Function. Software-Practice and Experience 23, 1 (1993), 1249-1265.

Digital Library

Google Scholar

[3]

Bentley, J.L., McIlroy, M.D., and Knuth, D.E. Programming Pearls: A Literate Program. Communications of the ACM 29, 6 (June 1986), 471-483.

Digital Library

Google Scholar

[4]

Bentley, J.L. and Saxe, J.B. Algorithms on Vector Sets. SIGACT News 11, 9 (Fall 1979), 36-39.

Digital Library

Google Scholar

[5]

Clampett, H.A. Jr. Randomized Binary Searching with Tree Structures. Communications of the A CM 7, 3 (March 1964), 163-165.

Digital Library

Google Scholar

[6]

Dijkstra, E.W. A Discipline of Programming. Prentice-Hall, Englewood Cliffs, N J, 1976.

Digital Library

Google Scholar

[7]

Flajolet, P. and Puech, C. Partial Match Retrieval of Multidimensional Data. Journal of the A CM 33, 2 (April 1986), 371-407.

Digital Library

Google Scholar

[8]

Floyd, R.W. and Rivest, R.L. Expected Time Bounds for Selection. Communications of the A CM 18, 3 (March 1975), 165-172.

Digital Library

Google Scholar

[9]

Hoare, C.A.R. Quicksort. Computer Journal 5, 1 (April 1962), 10-15.

Google Scholar

[10]

Kemighan, B.W. and Ritchie, D.M. The C Programming Language, Second Edition. Prentice-Hall, Englewood Cliffs, N J, 1988.

Digital Library

Google Scholar

[11]

Knuth, D.E. The Art of Computer Programming, volume 3: Sorting and Searching. Addison-Wesley, Reading, MA, 1975.

Digital Library

Google Scholar

[12]

Linderman, J.P. Theory and Practice in the Construction of a Working Sort Routine. Bell System Technical Journal 63, 8 (October 1984), 1827-1843.

Google Scholar

[13]

Manber, U. and Baeza-Yates, R. An Algorithm for String Matching with a Sequence of Don't Cares. Information Processing Letters 37, 3 (February 1991), 133-136.

Digital Library

Google Scholar

[14]

Manber, U. and Myers, G. Suffix Arrays: A New Method for On-Line String Searches. SIAM Journal on Computing 22 (1993), 935-948.

Digital Library

Google Scholar

[15]

Mcllroy, P.M., Bostic, K., and McIlroy, M.D. Engineering Radix Sort. Computing Systems 6, 1 (1993), 5-27.

Google Scholar

[16]

Mehlhorn, K. Data Structures and Algorithms 1: Sorting and Searching. Springer-Verlag, Berlin, 1984.

Google Scholar

[17]

Mehlhom, K. Dynamic Binary Search. SIAM Journal on Computing 8, 2 (May 1979), 175-198.

Google Scholar

[18]

Munro, J.I. and Raman, V. Sorting Multisets and Vectors In-Place. Proceedings of the Second Workshop on Algorithms and Data Structures, Springer Verlag Lecture Notes in Computer Science 519 ( 199 t), 473-480.

Google Scholar

[19]

Rivest, R.L. Partial-Match Retrieval Algorithms. SIAM Journal on Computing 5, 1 (1976), 19-50.

Google Scholar

[20]

Schoenhage, A.M., Paterson, M., and Pippenger, N. Finding the Median. Journal of Computer and Systems Sciences 13 (1976), 184-199.

Google Scholar

[21]

Sedgewick, R. Implementing Quicksort Programs. Communications of the ACM 21, t0 (October 1978), 847-857.

Digital Library

Google Scholar

[22]

Sedgewick, R. Quicksort With Equal Keys. SIAM J. Comp 6, 2 (June 1977), 240-267.

Google Scholar

[23]

Sedgewick, R. The Analysis of Quicksort Programs. Acta lnformatica 7 (1977), 327-355.

Google Scholar

[24]

Sleator, D.D. and Tarjan, R.E. Self-Adjusting Binary Search Trees. Journal of the A CM 32, 3 (July 1985), 652-686.

Digital Library

Google Scholar

[25]

Vaishnavi, V.K. Multidimensional Height-Balanced Trees. IEEE Transactions on Computers C-33, 4 (April 1984), 334-343.

Digital Library

Google Scholar

[26]

van Emden, M.H. Increasing the Efficiency of Quicksort. Communications of the A CM 13, 9 (September 1970), 563-567.

Digital Library

Google Scholar

[27]

Wegner, L.M. Quicksort for Equal Keys. IEEE Transactions on Computers C-34, 4 (April 1985), 362-367.

Google Scholar

Cited By

View all

Boffa AFerragina PTosoni FVinciguerra G(2024)CoCo-trieInformation Systems10.1016/j.is.2023.102316120:COnline publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1016/j.is.2023.102316
Barsky MGabor JConsens MThomo A(2020)Suffix rankProceedings of the VLDB Endowment10.14778/3407790.340786113:12(2787-2800)Online publication date: 14-Sep-2020
https://dl.acm.org/doi/10.14778/3407790.3407861
Munro JSinnamon CCzumaj A(2018)Time and space efficient representations of distributive latticesProceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3174304.3175306(550-567)Online publication date: 7-Jan-2018
https://dl.acm.org/doi/10.5555/3174304.3175306
Show More Cited By

Index Terms

Fast algorithms for sorting and searching strings

Recommendations

Fast algorithms to generate restricted classes of strings under rotation
Fast Searching in Packed Strings
Proceedings of the 20th Annual Symposium on Combinatorial Pattern Matching - Volume 5577

Given strings P and Q the exact string matching problem is to find all positions of substrings in Q matching P. The classical Knuth-Morris-Pratt algorithm [SIAM J. Comput., 1977] solves the string matching problem in linear time which is optimal if we ...
Generic algorithms for factoring strings
Information Theory, Combinatorics, and Search Theory

In this paper we describe algorithms for factoring words over sets of strings known as circ-UMFFs, generalizations of the well-known Lyndon words based on lexorder, whose properties were first studied in 1958 by Chen, Fox and Lyndon. In 1983 Duval ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SODA '97: Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms

January 1997

788 pages

ISBN:0898713900

Chairman:
Michael Saks

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 05 January 1997

Check for updates

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

94
Total Citations
View Citations
4,074
Total Downloads

Downloads (Last 12 months)114
Downloads (Last 6 weeks)17

Reflects downloads up to 29 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Boffa AFerragina PTosoni FVinciguerra G(2024)CoCo-trieInformation Systems10.1016/j.is.2023.102316120:COnline publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1016/j.is.2023.102316
Barsky MGabor JConsens MThomo A(2020)Suffix rankProceedings of the VLDB Endowment10.14778/3407790.340786113:12(2787-2800)Online publication date: 14-Sep-2020
https://dl.acm.org/doi/10.14778/3407790.3407861
Munro JSinnamon CCzumaj A(2018)Time and space efficient representations of distributive latticesProceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3174304.3175306(550-567)Online publication date: 7-Jan-2018
https://dl.acm.org/doi/10.5555/3174304.3175306
Abdel-Hafeez SGordon-Ross AAbubaker S(2018)A comparison-free sorting algorithm on CPUs and GPUsThe Journal of Supercomputing10.1007/s11227-018-2567-374:11(6369-6400)Online publication date: 1-Nov-2018
https://dl.acm.org/doi/10.1007/s11227-018-2567-3
Boissonnat JKarthik C. S. Tavenas S(2017)Building Efficient and Compact Data Structures for Simplicial ComplexesAlgorithmica10.1007/s00453-016-0207-y79:2(530-567)Online publication date: 1-Oct-2017
https://dl.acm.org/doi/10.1007/s00453-016-0207-y
Bingmann TEberle ASanders P(2017)Engineering Parallel String SortingAlgorithmica10.1007/s00453-015-0071-177:1(235-286)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.1007/s00453-015-0071-1
Aumüller MDietzfelbinger MKlaue P(2016)How Good Is Multi-Pivot Quicksort?ACM Transactions on Algorithms10.1145/296310213:1(1-47)Online publication date: 10-Oct-2016
https://dl.acm.org/doi/10.1145/2963102
Bille PFischer JGørtz IKopelowitz TSach BVildhøj H(2016)Sparse Text Indexing in Small SpaceACM Transactions on Algorithms10.1145/283616612:3(1-19)Online publication date: 25-Apr-2016
https://dl.acm.org/doi/10.1145/2836166
Jiang DWu SChen GOoi BTan KXu J(2016)epiCThe VLDB Journal — The International Journal on Very Large Data Bases10.1007/s00778-015-0393-225:1(3-26)Online publication date: 1-Feb-2016
https://dl.acm.org/doi/10.1007/s00778-015-0393-2
Ma HTseng YChen L(2016)A CMAC-based scheme for determining membership with classification of text stringsNeural Computing and Applications10.1007/s00521-015-1989-627:7(1959-1967)Online publication date: 1-Oct-2016
https://dl.acm.org/doi/10.1007/s00521-015-1989-6
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Fast algorithms to generate restricted classes of strings under rotation

Fast Searching in Packed Strings

Generic algorithms for factoring strings