View Full Document

Fast Algorithms for Sorting and Searching Strings



View the full content.
View Full Document
View Full Document

16 views

Unformatted text preview:

Fast Algorithms for Sorting and Searching Strings Jon L Bentley Abstract 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 1 Introduction Section 2 briefly reviews Hoare s 9 Quicksort and binary search trees We emphasize a well known isomorphism relating the two and summarize other basic facts The multikey algorithms and data structures are presented in Section 3 Multikey Quicksort orders a set of n vectors with k components each Like regular Quicksort it partitions its input into sets less than and greater than a given value like radix sort it moves on to the next field once the current input is known to be equal in the given field A node in a ternary search tree represents a subset of vectors with a partitioning value and three pointers one to lesser elements and one to greater elements as in a binary search tree and one to equal elements which are then processed on later fields as in tries Many of the structures and analyses have appeared in previous work but typically as complex theoretical constructions far removed from practical applications Our simple framework opens the door for later implementations The algorithms are analyzed in Section 4 Many of the analyses are simple derivations of old results Section 5 describes efficient C programs derived from the algorithms The first program is a sorting algorithm Bell Labs Lucent Technologies 700 Mountain Avenue Murray Hill NJ 07974 jlb research bell labs com



Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view Fast Algorithms for Sorting and Searching Strings and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Fast Algorithms for Sorting and Searching Strings and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?