【C++】文字列をコピーせずに文字列配列をソート順に出力する方法

はじめに

本記事では、「1つの文字列を別の文字列にコピーすることなく、文字列の配列をソートされた順序で出力する」というC++の問題を解説します。この問題では、ソート処理中に文字列を別の場所へコピーすることが禁止されています。

問題の確認

まず、具体例を見て概念を理解しましょう。

Input : {"Delhi", "Hyderabad", "Indore", "Mumbai", "Banglore"}
Output : Banglore, Delhi, Hyderabad, Indore, Mumbai

解説： 文字列は辞書順（レキシコグラフィック順）に並べ替えられます。そのため、「B」で始まる「Banglore」が先頭に、「M」で始まる「Mumbai」が最後に配置されます。

解決のためのアプローチ

文字列そのものの位置を入れ替えると、どうしてもコピー操作が必要になってしまいます。そこで有効なのが、インデックス配列を活用する方法です。

具体的には、以下の手順で処理を行います。

• 元の文字列配列の各要素に対応するインデックス（0, 1, 2, ...）を格納した配列を作成します。
• 参照先の文字列同士を比較しながら、インデックス配列をソートします。
• ソート後のインデックス配列の順序に従って、元の配列から文字列を出力します。

ここでは、要素を直接比較する選択ソートのアルゴリズムを採用します。

実装例

それでは、動作を示すプログラムを作成してみましょう。

#include <iostream>
using namespace std;
void sortedStringArray(string arr[], int n){
   int stringIndex[n];
   int i, j, min;
   for (i=0; i<n; i++)
   stringIndex[i] = i;
   for (i=0; i<n-1; i++){
      min = i;
      for (j=i+1; j<n; j++){
         if (arr[stringIndex[min]].compare(arr[stringIndex[j]]) > 0)
            min = j;
      }
      if (min != i){
         int temp = stringIndex[min];
         stringIndex[min] = stringIndex[i];
         stringIndex[i] = temp;
      }
   }
   for (i=0; i<n; i++)
      cout << arr[stringIndex[i]] << ", ";
}
int main(){
   string arr[] = {"Delhi", "Hyderabad", "Indore", "Mumbai", "Banglore"};
   int n = 5;
   sortedStringArray(arr, n);
   return 0;
}

出力結果

Banglore, Delhi, Hyderabad, Indore, Mumbai,

まとめ

この方法では、文字列データそのものは一切移動・コピーされず、インデックスの並べ替えだけでソートを実現できます。大きな文字列や大量のデータを扱う場合にも、コピーのコストを回避できるため、メモリやパフォーマンスの面で効率的なアプローチといえます。