Suppose, you are given an array of strings of different lengths, but the total number of characters over all the strings is n. Describe an algorithm using Counting Sort to sort the strings in alphabetic order (eg. algorithm < cs < hello) in O(n) time.

  • $\begingroup$ What are your thoughts on the question? $\endgroup$ – Yuval Filmus Feb 6 '20 at 1:46
  • $\begingroup$ The common assessment of the time required by Counting Sort has a second parameter in addition to some measure $n$ of the input. Please show how far you got. $\endgroup$ – greybeard Feb 6 '20 at 5:37

Here is the general idea:

  1. Sort all the strings according to their first character (refer to each string using an index to save time).

  2. Partition the strings according to their first character, and run recursively on each part (deleting in your mind the first character).

I'll let you work out the details.

  • $\begingroup$ I am thinking the same. But will it be still in O(n) ? $\endgroup$ – Hasan Shahriar Feb 6 '20 at 1:58
  • $\begingroup$ I think so. The complexity of the zeroth level of the recursion tree is the number of first characters. The complexity of the first level of the recursion tree is the number of second characters. And so on. $\endgroup$ – Yuval Filmus Feb 6 '20 at 2:08
  • $\begingroup$ Yes, it makes sense. Thank you. $\endgroup$ – Hasan Shahriar Feb 6 '20 at 2:16
  • $\begingroup$ The crux of Counting Sort is its dependence on "alphabet" size, say $S: |\Sigma|$. With "single letter strings", this should amount to $O(n+S)$, with two strings of length $n/2$, I see $O(nS)$ $\endgroup$ – greybeard Feb 6 '20 at 6:05
  • $\begingroup$ Alphabet is constant. $\endgroup$ – Yuval Filmus Feb 6 '20 at 6:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.