1997 · 399 citations · 20 references
ComputingComputer ScienceAlgorithmsComputer ArchitectureData StructuresHash TablesSearching AlgorithmsSorting AlgorithmsSorting ProblemsString AlgorithmsBinary Search TreesHashingPractical UtilityQuicksortString IndexingString SearchString SearchingString Sorting
The basic ideas behind the algorithms date back to the 1960s, but their practical utility has been overlooked. The study presents theoretical algorithms for sorting and searching multikey data, practical C implementations for character string applications, and extensions to complex string problems such as partial‑match searching. The authors develop theoretical multikey sorting and searching algorithms and implement them in C for character string applications, also extending the methods to partial‑match searching. The sorting algorithm combines Quicksort and radix sort and rivals the best C sort codes, while the searching algorithm merges tries and binary search trees and outperforms hashing and other common methods.
We present theoretical algorithms for sorting and searching multikey data, and derive from them practical C implementations for applications in which keys are character strings. The sorting algorithm blends Quicksort and radix sort; it is competitive with the best known C sort codes. The searching algorithm blends tries and binary search trees; it is faster than hashing and other commonly used search methods. The basic ideas behind the algorithms date back at least to the 1960s, but their practical utility has been overlooked. We also present extensions to more complex string problems, such as partial-match searching.
20
Suffix Arrays: A New Method for On-Line String Searches
Udi Manber, Gene Myers · SIAM Journal on Computing · 1993 · 2K citations
Self-adjusting binary search trees
Daniel D. Sleator, Robert E. Tarjan · Journal of the ACM · 1985 · 1.2K citations · Full text
Implementing Quicksort programs
Robert Sedgewick · Communications of the ACM · 1978 · 290 citations
Expected time bounds for selection
Robert W. Floyd, Ronald L. Rivest · Communications of the ACM · 1975 · 280 citations · Full text
Partial-Match Retrieval Algorithms
Ronald L. Rivest · SIAM Journal on Computing · 1976 · 247 citations