Designing an algorithm to sort n strings in O(dn)

Question

How can I design an algorithm to sort n strings in O(dn) where d is the #of characters in a longest string?

Community · Accepted Answer · 2017-05-23 12:06:53Z

1

You can use a trie.

Create an empty trie.
Loop over all strings, and place them in it.
Iterate over all the trie's values in order, and output them (see Trie complexity and searching as suggested below by Jean-Baptiste Yunès).

The complexity of 1 is constant. The complexity of each of 2 and 3 is O(dn).

edited May 23, 2017 at 12:06

CommunityBot

11 silver badge

answered Oct 5, 2016 at 5:21

Ami Tavory

76.7k13 gold badges152 silver badges196 bronze badges

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

4 Comments

Saurav Sahu Over a year ago

3rd point is not clear. How are you making sure the strings are sorted

Ami Tavory Over a year ago

@SauravSahu It's a pretty simple recursive function (see here an implementation). Starting at the node, recursively visit all children in order, while keeping track of current prefix. When you hit a leaf, output the total string along the path.

Jean-Baptiste Yunès Over a year ago

Complement: stackoverflow.com/questions/13032116/…

Ami Tavory Over a year ago

@Jean-BaptisteYunès Thanks for the useful link! Added inline

Collectives™ on Stack Overflow

Designing an algorithm to sort n strings in O(dn)

1 Answer 1

4 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related