Sorting a string lexicographically

Question

I have N strings and want to sort them in lexicographical order (dictionary order). How can I do that as N is quite big 1 <= N <= 1e5 and size of each string is 1 <= |s| <= 1000? Also the string is only made of small English alphabets.

I figured out one method but test cases are giving time limit exceeded. Is there a better approach?

Answer 1

Yes, there are two ways.

1. Use HASHING.

HOW TO USE ?

• Create a simple integer array(hash[]) of size 26. Each of its index will denote an alphabet, considering your string is only comprised of small alphabets.
• Initialize the array to zero.
• Now traverse the string and for each occurred alphabet in string add its frequency by one in hash[]. For example if 'a' occurred in string then hash[0] = hash[0] + 1;
• After you are finished with above step. you will have all characters frequency in hash.
• Now traverse your hash[] and for each index i print all characters until hash[i] becomes zero. It is because, as you want to sort string lexicographically the best way is print all 'a' then all 'b' and so on present in string.
• Time complexity for above method is O(n*2s).
• Below is the program

int hash[26]={0};
for( int i = 0 ; i < s.length() ; i++ ) // s.length() returns string length
{
   hash[s[i]-97] += 1; // s[i] - 97 actually returns index for the character
}
char ch;
for( int i = 0 ; i < 26 ; i++ )
{
   ch = i+97; // making the character required
   while(hash[i]) { cout << ch; hash[i] -= 1; } // printing it its frequency times
}

2. Use nlog(n) sorting

• In C++ you can use sort() function to sort the strings also.

HOW ?

• Just write sort( s.begin() , s.end() ) ;
• Complexity of this method is O(n*|s|log(|s|))
• Code is below

string s;
cin >> s;
sort( s.begin(); s.end() );
cout << s << endl;