文字列の文字をソートする：効率的な方法とコード例 (C++, C, Java, Python, C#, JavaScript)

文字列内の文字をアルファベット順にソートする方法はいくつかあります。この記事では、さまざまなプログラミング言語での実装例とともに、最も効率的なアプローチについて説明します。

なぜ文字のソートが重要なのか？

データの整理は、アルゴリズムの効率を高める上で不可欠です。特に文字列処理において、ソートされた文字列は、アナグラム検出、データ検証、テキスト分析など、さまざまな用途で使用されます。

ナイーブなアプローチ：O(n Log n) 時間

![アルゴリズムの複雑さ](https://media.geeksforgeeks.org/auth-dashboard-uploads/Group-arrow.svg "クイックソートアルゴリズム")

最も単純な方法は、クイックソートやマージソートなどの一般的なソートアルゴリズムを使用することです。これは理解しやすいですが、効率の面では最適ではありません。 具体的には以下のような手順で行います。

1. 文字列を文字配列に変換します。
2. 配列をソートします。（例えば、Arrays.sort(arr)など）
3. ソートされた配列を文字列に戻します。

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

using namespace std;

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

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

より高速な方法は、文字の頻度をカウントし、それを使用してソートされた文字列を構築することです。これは、文字セットが比較的小さい場合に特に効果的です（たとえば、小文字のアルファベットのみの場合）。

• 26文字（'a'〜'z'）の要素を持つハッシュ配列（または頻度配列）を作成します。
• 入力文字列を走査し、各文字の出現回数を対応する配列要素に保存します。
• 頻度配列を走査し、各文字を必要な回数だけ出力します。

#include <iostream>
#include <string>

using namespace std;

const int MAX_CHAR = 26;

void sortString(string& s) {
  int charCount[MAX_CHAR] = {0};

  for (char c : s) {
    charCount[c - 'a']++;
  }

  for (int i = 0; i < MAX_CHAR; i++) {
    for (int j = 0; j < charCount[i]; j++) {
      cout << (char)('a' + i);
    }
  }
  cout << endl;
}

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

各言語での実装例

以下に、C, Java, Python, C#, JavaScript での実装例を示します。

C

#include <stdio.h>
#include <string.h>

#define MAX_CHAR 26

void sortString(char s[]) {
    int charCount[MAX_CHAR] = {0};
    int n = strlen(s);

    for (int i = 0; i < n; i++) {
        charCount[s[i] - 'a']++;
    }

    for (int i = 0; i < MAX_CHAR; i++) {
        for (int j = 0; j < charCount[i]; j++) {
            printf("%c", 'a' + i);
        }
    }
    printf("\n");
}

int main() {
    char s[] = "geeksforgeeks";
    sortString(s);
    return 0;
}

Java

import java.util.Arrays;

public class StringSort {
    public static void main(String[] args) {
        String s = "geeksforgeeks";
        char[] arr = s.toCharArray();
        Arrays.sort(arr);
        s = new String(arr);
        System.out.println(s);
    }
}

Python

s = "geeksforgeeks"
s = ''.join(sorted(s))
print(s)

C#

using System;
using System.Linq;

public class StringSort {
    public static void Main(string[] args) {
        string s = "geeksforgeeks";
        char[] arr = s.ToCharArray();
        Array.Sort(arr);
        s = new string(arr);
        Console.WriteLine(s);
    }
}

JavaScript

let s = "geeksforgeeks";
s = s.split('').sort().join('');
console.log(s);

まとめ

この記事では、文字列内の文字をソートする2つのアプローチについて説明しました。 ナイーブなアプローチは単純ですが、O(n Log n)の時間複雑度を持ちます。 より効率的なアプローチはO(n)の時間複雑度を持ち、一定の文字セットサイズに最適です。 プログラミングタスクの特定の制約に基づいて、最適なアプローチを選択してください。適切なアルゴリズムを選択することで、アプリケーションのパフォーマンスを大幅に向上させることができます。