CODEWITHSUNDEEP
algorithmsortingcomputer-science
Dan
Dan

Reputation: 139

How can I sort n words with length k in linear time?

I want to implement an algorithm to sort n words of length k, the words will contain only English words (so from a-z).

I tried to use the counting sort by casting the first element of the word -> character to its integer representation and then use Counting Sort (Linear Time Sorting), this kind of works but it is only sorting the first character i.e when two or more words have the same first character then they are not sorted by their second character?

Can someone guide me or give me a hint for another approach which will let me sort these n words in linear time?

Upvotes: 0

Views: 245

Answers (1)

William Li
William Li

Reputation: 11

Radix sort is probably the way to go - it will stable sort each word by the i-th letter. Since you're working with characters, you're essentially already working in the appropriate radix!

Upvotes: 1

Related Questions