C++で大文字・小文字を交互に並べる文字列ソートの実装方法

文字列とは文字の配列です。この問題は、文字列の各要素を「大文字と小文字が交互に現れるように」並べ替えることを目的としています。

問題の概要

「交互 小文字・大文字 文字列ソート」とは、大文字と小文字が混在し、順序がバラバラの文字列が与えられたとき、それを大文字と小文字が交互の位置に配置され、かつそれぞれがソート済みの順序になっている状態に並べ替える問題です。

具体例を見て理解を深めましょう。

入力 : aFegrAfStRzsV
出力 : AaFeRfSgVrstz
説明 :
大文字 : A F R S V
小文字 : a e f g r s t z

大文字と小文字はそれぞれ昇順に整列されているため、あとは両者を交互に組み合わせれば答えが得られます。

問題の内容が理解できたところで、次は解法を考えていきましょう。一つのアプローチとして、大文字用と小文字用にそれぞれソート済みの配列を作成し、最終的な文字列へ交互に配置していくという方法があります。この考え方に基づいたアルゴリズムを以下に示します。

アルゴリズム

ステップ1 : 配列 lowercount[] に、すべての小文字をソート済みの順序で格納する。
ステップ2 : 配列 uppercount[] に、すべての大文字をソート済みの順序で格納する。
ステップ3 : 両方の配列から値を交互に取り出し、最終的な文字列を構築する。
ステップ4 : 結果の配列を出力する。

C++による実装例

#include <iostream>
using namespace std;
#define MAX 26
void alternateULSort(string& s) ;
int main(){
    string str = "aFegrAfStRzsV";
    cout<<"The unsorted string is : "<<str;
    cout<<"\nThe alternate lower upper sorted string is ";
    alternateULSort(str);
    cout << str << "\n";
}
void alternateULSort(string& s){
    int n = s.length();
    int lowerCount[MAX] = { 0 }, upperCount[MAX] = { 0 };
    for (int i = 0; i < n; i++) {
        if (isupper(s[i]))
            upperCount[s[i] - 'A']++;
        else
            lowerCount[s[i] - 'a']++;
    }
    int i = 0, j = 0, k = 0;
    while (k < n) {
        while (i < MAX && upperCount[i] == 0)
            i++;
        if (i < MAX) {
            s[k++] = 'A' + i;
            upperCount[i]--;
        }
        while (j < MAX && lowerCount[j] == 0)
            j++;
        if (j < MAX) {
            s[k++] = 'a' + j;
            lowerCount[j]--;
        }
    }
}

実行結果

The unsorted string is : aFegrAfStRzsV
The alternate lower upper sorted string is AaFeRfSgVrstz

計算量のポイント

この実装ではカウントソートの考え方を応用しています。各文字の出現回数を長さ26の固定サイズ配列に記録するため、時間計算量は O(n)、追加で必要なメモリも定数サイズ(O(1))に抑えられます。比較ベースの一般的なソート(O(n log n))よりも高速に動作する点が大きな特徴です。