文字列の文字をソートする方法：効率的なアルゴリズムと実装

文字列内の文字をソートする方法は、プログラミングにおける基本的なタスクです。この記事では、さまざまなアプローチを解説し、それぞれの時間計算量と実装例を提供します。効率的なアルゴリズムを使用することで、パフォーマンスを大幅に向上させることができます。

ナイーブなアプローチ (O(n log n))

最も簡単な方法は、クイックソートやマージソートなどの既存のソートアルゴリズムを使用することです。

• メリット: 実装が容易で、ほとんどのプログラミング言語で利用可能です。
• デメリット: より効率的なアプローチと比較して、時間計算量が大きくなります。

#include <iostream>
#include <string>
#include <algorithm>

int main() {
    std::string s = "geeksforgeeks";
    std::sort(s.begin(), s.end());
    std::cout << s << std::endl; // 出力: eeeefggkkorss
    return 0;
}

効率的なアプローチ (O(n))

26個のユニークな文字しか存在しないという事実に着目します（'a'〜'z'）。文字の出現回数を記録するために、ハッシュ配列を使用します。

• メリット: 時間計算量がO(n)で、非常に効率的です。
• デメリット: 英小文字以外の文字には適用できません。

#include <iostream>
#include <string>

const int MAX_CHAR = 26;

void sortString(std::string& s) {
    int charCount[MAX_CHAR] = {0};
    for (int i = 0; i < s.length(); i++) {
        charCount[s[i] - 'a']++;
    }
    for (int i = 0; i < MAX_CHAR; i++) {
        for (int j = 0; j < charCount[i]; j++) {
            std::cout << (char)('a' + i);
        }
    }
    std::cout << std::endl;
}

int main() {
    std::string s = "geeksforgeeks";
    sortString(s); // 出力: eeeefggkkorss
    return 0;
}

ハッシュ法を利用した効率的なソート：詳細な解説

このアプローチは、文字列内の各文字の出現回数をカウントし、そのカウントに基づいてソートされた文字列を再構築します。

1. カウント配列の初期化: 26個の要素を持つ整数型のcharCount配列を作成し、すべての要素を0で初期化します。
2. 文字のカウント: 入力文字列を走査し、各文字について、対応するcharCount配列の要素をインクリメントします。 例えば、文字'a'のASCII値は97なので、'a' - 'a' = 0となり、charCount[0]がインクリメントされます。
3. ソートされた文字列の構築: charCount配列を走査し、各文字のカウント回数だけ、その文字を出力します。

まとめ

文字列の文字をソートするには、複数の方法があります。最も適切な方法は、文字列のサイズとパフォーマンス要件によって異なります。 小さな文字列の場合は、ナイーブなアプローチで十分かもしれません。 大きな文字列の場合は、効率的なアプローチの方が適しています。