Самый быстрый способ сортировки |O(n)

Алгоритмы

Самый быстрый способ сортировки |O(n)

Часто задаваемый вопрос на собеседовании

Некоторые алгоритмы могут сортировать за время O(n²), например, пузырьковая сортировка, сортировка вставками, а затем есть алгоритмы, такие как сортировка слиянием, которые могут выполнять это за время O(nlog(n)). Эти алгоритмы работают лучше всего, когда нет ограничений на символы/целые числа. Но когда мы сортируем строку, скажем, строчных букв, часто бывает, что символы могут быть только между az. Мы можем отсортировать такую ​​последовательность за время O(n). Мы увидим, как…

Сначала мы определяем массив размером 26 и инициализируем его 0

int count[26] = {0};

После этого мы обходим строку один раз и увеличиваем количество символов соответствующего индекса в массиве count.

for(char c : str){
      count[c - 'a']++;
}

Наконец, мы перемещаемся по массиву count и создаем отсортированную строку, добавляя i-й символ count[i] раз.

str = "";
for(int i=0;i<26;++i){
     for(int j=0;j<count[i];++j){
           str.push_back(i+'a');
      }
}

Окончательный код

#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

Подпишитесь на бинарный мир, чтобы узнать больше

Подпишитесь на нас в facebook , instagram и посетите наш веб-сайт.