_comfortably_numb's blog

Sorting A vector of strings

By _comfortably_numb, history, 6 years ago, In English

Recently I faced few problems where I needed to use a map of strings or sort a vector of strings.

The number of strings can be upto 10^5, but the summation of lengths of the strings won't be larger than 10^5.

Now, I wonder what is the complexity of this sorting ? And can you please explain why ?

  • Vote: I like it
  • +32
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it +34 Vote: I do not like it

It's easier to analyze if you maintain a set (sorted) of the strings and insert them one by one. The length of the currently inserted string is L. Since we do comparisons with it and other already inserted strings, the complexity is worstcase , and so the total cost of inserting all strings is .

→ Reply
»
6 years ago, # |
  Vote: I like it +34 Vote: I do not like it

The time complexity of comparing two strings s1 and s2 of length n1 and n2 is clearly, . So, the worst case input corresponds to input strings having equal length m. Assume the input consists of n strings. The length of each string ( in the case of all strings having equal length ) will be . The 105 comes into the picture to satisfy the constraints in your question. For the case of sorting, if there are n elements, the total number of comparisons is . Here, we also need to account for the comparison between two strings, which, in our case, is m. Multiplying we get, .

→ Reply