Linear-time sorting algorithm for strings?

Question

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.

The person who gives you an answer to this in general will get an accepted answer and a few million dollars. You can't do sorting (in general) in O(n), without making some serious CS innovations. — Oleksi
– Oleksi, Commented Jun 12, 2012 at 19:38
@Oleksi: You can do it in this instance. The OP isn't exactly asking about the general case. — Louis Wasserman
– Louis Wasserman, Commented Jun 12, 2012 at 19:40
take care about definition of "n". here "n" is not number of elements, but number of total characters of all strings! — Ehsan Khodarahmi
– Ehsan Khodarahmi, Commented Jun 12, 2012 at 19:40
@EhsanKhodarahmi: So you're saying that if you have m strings each 1000 characters long, you expect to be able to sort them in O(m) time? (since O(1000*m) is the same as O(m)) — NPE
– NPE, Commented Jun 12, 2012 at 19:44

templatetypedef · Accepted Answer · 2012-06-12 19:45:03Z

11

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!

edited Jun 12, 2012 at 19:45

answered Jun 12, 2012 at 19:38

templatetypedef

376k112 gold badges954 silver badges1.1k bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Bill Gage · Accepted Answer · 2020-10-09 15:46:59Z

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.

Stefan Savev · Accepted Answer · 2015-10-14 08:21:16Z

0

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.

edited Oct 14, 2015 at 8:21

answered Oct 10, 2015 at 13:56

Stefan Savev

8591 gold badge6 silver badges7 bronze badges

Collectives™ on Stack Overflow

Linear-time sorting algorithm for strings?

3 Answers 3

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related