Algorithms
The fastest way to sort |O(n)
Commonly asked interview question
Some algorithms can sort in O(n²) time like the bubble sort, insertion sort, and then there are algorithms like merge sort that can do it in O(nlog(n)) time. These algorithms work the best when there is no bound on the characters/integers. But when we are sorting a string of let’s say lowercase alphabets there is abound that the characters can only be between a-z. We can sort this kind of sequence in O(n) time. We will see how…
First we define a array of size 26 and initialize it by 0
int count[26] = {0};After that, we traverse the string once and increase the character count of the corresponding index in the count array.
for(char c : str){
count[c - 'a']++;
}Finally, we move through the count array and construct the sorted string by adding ith character count[i] times.
str = "";for(int i=0;i<26;++i){
for(int j=0;j<count[i];++j){
str.push_back(i+'a');
}
}
The final code
#include <iostream>using namespace std;int main()
{
string str = "manas";
int count[26] = {0};
for(char c : str){
count[c - 'a']++;
}
str = "";
for(int i=0;i<26;++i){
for(int j=0;j<count[i];++j){
str.push_back(i+'a');
}
}
cout<<str;
return 0;
}OUTPUT : aamns
Follow the binary realm for more
