Sorting variable-length items / Algorithms

Question

I have been studying for my Algorithms midterm and there is this question in the book that I came across about sorting variable length items :

You are given an array of strings, where different strings may have different numbers of characters, but the total number of characters over all the strings is n. Show how to sort the strings in O(n) time.

I found many answers online but they weren't very clear in their explanations so I would really appreciate it if you could take the time to explain to me more in depth what this answer suggests should be done to sort the strings in O(n) time:

Groups the strings by length and order the groups
Starting i on the maximum length and going down to 1, perform counting sort on the ith character. Make sure to include only groups that have an ith character. If the groups are subsequent subarrays in the original array, we’re perform

(You should be explicit whether this is about items with variable length keys or about items with variable length, which may make "exchange" a challenge.) — greybeard
– greybeard, Commented Sep 25, 2016 at 12:35

Attila Bujdosó · Accepted Answer · 2017-03-23 20:06:32Z

2

This is what you are searching for:https://en.wikipedia.org/wiki/Radix_sort

In simple words:

You start sorting by the first digit of the strings. This can be done in one pass O(N), since you do not need to compare each element with others. You just need to remember the starting and ending position of each group of values in the array. For example all strings starting with 'g' are located in array positions 35 to 500. When you find a string stating with 'g' you add it to the end of this group.

In the next phase you do the same for each of these groups.

As you can see, it takes O(M*N) where M is the string length and N is the number of strings. In your case your N is total length of all strings so it's O(N).

Although you have strings in different lengths you can still keep the O(N), because at some point items that are too short will not need to be re-sorted.

edited Mar 23, 2017 at 20:06

Attila Bujdosó

31 bronze badge

answered Sep 25, 2016 at 8:49

O_Z

1,5639 silver badges11 bronze badges

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

Collectives™ on Stack Overflow

Sorting variable-length items / Algorithms

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related