文字列の文字をソートする方法【複数のプログラミング言語での実装例】

この記事では、与えられた文字列の文字をソートする方法について解説します。文字列をソートすることで、文字の出現頻度分析や、アナグラム判定など、さまざまな用途に活用できます。

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

最も単純な方法は、クイックソートやマージソートのような一般的なソートアルゴリズムを使用することです。

メリット: 実装が簡単で、多くのプログラミング言語で標準ライブラリとして提供されています。
デメリット: 文字列の長さが長くなると、計算時間が比較的長くなります。

以下はC++、C、Java、Python、C#、JavaScriptでの実装例です。

C++

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

using namespace std;

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

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

int compare(const void *a, const void *b) {
    return (*(char*)a - *(char*)b);
}

void sortString(char *str) {
    int n = strlen(str);
    qsort(str, n, sizeof(char), compare);
    printf("%s", str);
}

int main() {
    char s[] = "geeksforgeeks";
    sortString(s); // 出力: eeeefggkkorss
    return 0;
}

Java

import java.util.Arrays;

public class GfG {
    public static void main(String[] args) {
        String s = "geeksforgeeks";
        char[] arr = s.toCharArray();
        Arrays.sort(arr);
        s = new String(arr);
        System.out.print(s); // 出力: eeeefggkkorss
    }
}

Python

s = "geeksforgeeks"
s = ''.join(sorted(s))
print(s) # 出力: eeeefggkkorss

using System;

class GfG {
    static void Main() {
        string s = "geeksforgeeks";
        char[] arr = s.ToCharArray();
        Array.Sort(arr);
        s = new string(arr);
        Console.Write(s); // 出力: eeeefggkkorss
    }
}

JavaScript

let s = "geeksforgeeks";
s = s.split('').sort().join('');
console.log(s); // 出力: eeeefggkkorss

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

より効率的な方法は、文字の出現回数をカウントし、その情報に基づいてソートされた文字列を生成することです。この方法は、文字の種類が限られている場合に特に有効です。例えば、アルファベットの小文字のみを扱う場合、26個の要素を持つ配列で各文字の出現回数を記録できます。

メリット: 文字列の長さに関わらず、高速にソートできます。特に、文字の種類が少ない場合に効果を発揮します。
デメリット: 文字の種類が多い場合、メモリ使用量が増加する可能性があります。

以下はC++とCでの実装例です。

C++

#include <iostream>
#include <string>

using namespace std;

const int MAX_CHAR = 26;

void sortString(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++) {
           cout << (char)('a' + i);
        }
    }
}

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

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

#define MAX_CHAR 26

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

    for (int i = 0; i < strlen(s); 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);
        }
    }
}

int main() {
    char s[] = "geeksforgeeks";
    sortString(s); // 出力: eeeefggkkorss
    return 0;
}

まとめ

文字列の文字をソートする方法は複数存在します。最も適切な方法は、文字列の長さ、文字の種類、およびパフォーマンス要件によって異なります。大量のデータを処理する際には、計算量が少ないO(n)の効率的なアプローチを検討すると良いでしょう。

文字列の文字をソートする方法【複数のプログラミング言語での実装例】

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

最も単純な方法は、クイックソートやマージソートのような一般的なソートアルゴリズムを使用することです。

メリット: 実装が簡単で、多くのプログラミング言語で標準ライブラリとして提供されています。
デメリット: 文字列の長さが長くなると、計算時間が比較的長くなります。

以下はC++、C、Java、Python、C#、JavaScriptでの実装例です。

C++

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

using namespace std;

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

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

int compare(const void *a, const void *b) {
    return (*(char*)a - *(char*)b);
}

void sortString(char *str) {
    int n = strlen(str);
    qsort(str, n, sizeof(char), compare);
    printf("%s", str);
}

int main() {
    char s[] = "geeksforgeeks";
    sortString(s); // 出力: eeeefggkkorss
    return 0;
}

Java

import java.util.Arrays;

public class GfG {
    public static void main(String[] args) {
        String s = "geeksforgeeks";
        char[] arr = s.toCharArray();
        Arrays.sort(arr);
        s = new String(arr);
        System.out.print(s); // 出力: eeeefggkkorss
    }
}

Python

s = "geeksforgeeks"
s = ''.join(sorted(s))
print(s) # 出力: eeeefggkkorss

using System;

class GfG {
    static void Main() {
        string s = "geeksforgeeks";
        char[] arr = s.ToCharArray();
        Array.Sort(arr);
        s = new string(arr);
        Console.Write(s); // 出力: eeeefggkkorss
    }
}

JavaScript

let s = "geeksforgeeks";
s = s.split('').sort().join('');
console.log(s); // 出力: eeeefggkkorss

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

メリット: 文字列の長さに関わらず、高速にソートできます。特に、文字の種類が少ない場合に効果を発揮します。
デメリット: 文字の種類が多い場合、メモリ使用量が増加する可能性があります。

以下はC++とCでの実装例です。

C++

#include <iostream>
#include <string>

using namespace std;

const int MAX_CHAR = 26;

void sortString(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++) {
           cout << (char)('a' + i);
        }
    }
}

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

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

#define MAX_CHAR 26

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

    for (int i = 0; i < strlen(s); 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);
        }
    }
}

int main() {
    char s[] = "geeksforgeeks";
    sortString(s); // 出力: eeeefggkkorss
    return 0;
}

文字列の文字をソートする方法【複数のプログラミング言語での実装例】

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

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

まとめ

文字列の文字をソートする方法【複数のプログラミング言語での実装例】

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

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

まとめ

関連する記事