文字列を英数字順（辞書順）に並べ替えるアルゴリズムとC++実装例

与えられた文字列のリストを、英数字順（辞書順）に並べ替えるアルゴリズムを解説します。例えば「Apple」「Book」「Aim」という3つの単語がある場合、これらは「Aim」「Apple」「Book」の順に並べ替えられます。また、リストに数値が含まれている場合は、文字コードの順序に従って、英字の文字列よりも前に配置されます。

入力と出力

Input:
文字列のリスト: Ball Apple Data Area 517 April Man 506
Output:
ソート後の文字列: 506 517 Apple April Area Ball Data Man

アルゴリズム

ここでは、隣り合う要素同士を比較して必要に応じて入れ替える「バブルソート」の仕組みを利用します。大まかな流れは以下のとおりです。

sortStr(strArr, n)

入力: ソート対象のすべての文字列のリスト、および要素数

出力: 英数字順に並べ替えられた文字列

Begin
    for round := 1 to n-1, do
      for i := 0 to n-round, do
         res := compare str[i] and str[i+1]     //正・負・0 のいずれかを返す
         if res > 0, then
            swap str[i] and str[i+1]            //2つの文字列を入れ替える
      done
   done
End

文字列の比較には compare() 関数を使用します。この関数は2つの文字列を辞書順で比較し、前の文字列の方が大きければ正の値、小さければ負の値、等しければ 0 を返します。比較結果が正の値となったときだけ隣接する2つの文字列を入れ替えていくことで、リスト全体が昇順に整列していきます。

C++による実装例

#include<iostream>
#define N 8
using namespace std;

void display(int n, string str[]) {
    for(int i = 0; i<n; i++)
        cout << str[i] << " ";          //配列内の文字列を表示
    cout << endl;
}

void sortStr(int n, string str[]) {
    int i, round, res;
    for(round = 1; round<n; round++)
        for(i = 0; i<n-round; i++) {
            res = str[i].compare(str[i+1]);
            if(res > 0)
                swap(str[i], str[i+1]); //文字列を入れ替える
        }
}

main() {
    string str[N] = {"Ball", "Apple", "Data", "Area", "517", "April", "Man", "506"};
    cout << "Strings before sort:" << endl;
    display(N, str);
    sortStr(N, str);
    cout << "Strings after sort:" << endl;
    display(N, str);
}

実行結果

Strings before sort:
Ball Apple Data Area 517 April Man 506
Strings after sort:
506 517 Apple April Area Ball Data Man

実行結果を見ると、数値の「506」と「517」が先頭に来て、その後ろに英字の文字列が「Apple」「April」「Area」「Ball」「Data」「Man」の順に並んでいることが確認できます。これは、ASCIIコードでは数字（'0'〜'9'）が英大文字（'A'以降）よりも小さい値を持つためです。したがって、数値文字列は常に英字の文字列より前方に配置されます。