CODEWITHSUNDEEP
javaalgorithmsortingcomplexity-theorybig-o
Ehsan Khodarahmi
Ehsan Khodarahmi

Reputation: 4932

Linear-time sorting algorithm for strings?

I have an array of strings, each one with a different length. e.g:

s[0] = "sSWXk"
s[1] = "qCk"
s[2] = "sOQQXPbk"
.
.
.
s[x] = "KVfdQk";

I also am given that

n = s[0].length() + s[1].length() + ... + s[x].length()

I need a sorting algorithm with time complexity O(n) for sorting these strings lexicographically, so that (for example)

a < ab < b < bbc < c < ca

Any suggestions? The time complexity is the essential requirement in the algorithm.

Upvotes: 1

Views: 4672

Answers (3)

Bill Gage
Bill Gage

Reputation: 21

I've had a similar test question, which I got incorrect, but it has bugged me since then. So I kept looking into it, and I think there are two other methods that might produce results in linear time. One is to treat the strings as a series of integers with a base of 26 and use radix sort on the array after padding the strings to be of equal length (in some way - there's probably a slick way to do this without increasing storage space drastically, I just haven't worked out the details). I haven't built an example or tested it, so I can't say with certainty this would work, but the principle of it seems sound. Another method would be bucket sort - using a 26 element array that contain pointers to 26 lists (the buckets). Sort each string into the appropriate the bucket-linked lists (those starting with 'a' into the list pointed at by the first array element, etc.) Then sort each list using a standard O(n log n) method. I don't fully understand the math, but according to Cormen's textbook "Introduction to Algorithms", using bucket sort in this way winds up having a linear time complexity. It seems the space would be larger than the Radix-style method, though, so long as the right-padding requirement could be met without actually allocating a bunch of storage for it.

Upvotes: 1

Stefan Savev
Stefan Savev

Reputation: 859

Because this is a homework problem I can only give a hint. Hint: Use a modified version of counting sort. It's practical if we assume a char is 8 bits.

Upvotes: 0

templatetypedef
templatetypedef

Reputation: 373482

There is a data structure called a trie that is optimally suited for this. If you insert all the words into the trie and then do a DFS over the trie, you will get the words back in sorted order. Doing so takes time O(n) as well, where n is the total number of characters in all the strings.

Since I assume that this is homework, I'll leave the details of how to implement the trie as an exercise. :-)

Hope this helps!

Upvotes: 11

Related Questions