【C++】配列内のxの倍数である要素だけを昇順に再配置するプログラム

本記事では、整数型配列「int arr[]」と整数型変数「x」が与えられたとき、配列の中で「x」で割り切れる要素だけを取り出して昇順に並べ替え、元々その要素があった位置に戻すC++のプログラムを解説します。xの倍数ではない要素は、元の位置にそのまま残ります。

入出力のシナリオ例

入力 − int arr[] = {4, 24, 3, 5, 7, 22, 12, 10}, int x = 2

出力 − x=2の倍数である要素を昇順に再配置した結果: 4 10 3 5 7 12 22 24

解説 − 整数型配列 {4, 24, 3, 5, 7, 22, 12, 10} と x = 2 が与えられています。まず、配列の中から2で割り切れる要素、すなわち 4, 24, 22, 12, 10 を抽出します。次に、これらの要素を昘順に並べ替えて元の位置に戻すと、4, 10, 3, 5, 7, 12, 22, 24 となり、これが最終的な出力です。

入力 − int arr[] = {4, 24, 3, 5, 7, 22, 12, 10}, int x = 3

出力 − x=3の倍数である要素を昘順に再配置した結果: 4 3 12 5 7 22 24 10

解説 − 同じ配列に対して x = 3 が与えられています。まず、配列の中から3で割り切れる要素、すなわち 3, 24, 12 を抽出します。これらを昘順に並べ替えて元の位置に戻すと、4, 3, 12, 5, 7, 22, 24, 10 となり、これが最終的な出力です。

プログラムで使用するアプローチ

• 整数型配列を宣言し、配列のサイズを計算して変数 size に格納します。また、基準となる整数型変数 x を宣言します。
• データを関数 Rearrange_Elements(arr, size, x) に渡します。
• 関数 Rearrange_Elements(arr, size, x) の内部では以下の処理を行います。
  • 整数型の値を格納する vector 型の変数 vec を作成します。
  • i を 0 から size 未満まで FOR ループで回し、arr[i] % x == 0 であれば arr[i] を vec に push_back します。
  • C++ STL の sort メソッドを使い、begin() と end() を引数として渡してベクターを昘順にソートします。
  • 再び i を 0 から size 未満まで FOR ループで回し、arr[i] % x == 0 であれば arr[i] に vec[j++] を代入します。
  • for ループで配列の先頭要素から最後の要素まで走査し、結果を出力します。

サンプルコード

#include <bits/stdc++.h>
using namespace std;
void Rearrange_Elements(int arr[], int size, int x){
   vector<int> vec;
   int j = 0;
   for(int i = 0; i < size; i++){
      if(arr[i] % x == 0){
         vec.push_back(arr[i]);
      }
   }
   sort(vec.begin(), vec.end());
   for (int i = 0; i < size; i++){
      if(arr[i] % x == 0){
         arr[i] = vec[j++];
      }
   }
   cout<<"x = "<<x<<" の倍数である要素を昘順に再配置した結果: ";
   for(int i = 0; i < size; i++){
      cout << arr[i] << " ";
   }
}
int main(){
   int arr[] = {4,24, 3, 5, 7, 22, 12, 10};
   int x = 2;
   int size = sizeof(arr) / sizeof(arr[0]);
   Rearrange_Elements(arr, size, x);
   return 0;
}

実行結果

上記のコードを実行すると、以下の出力が得られます。

x = 2 の倍数である要素を昘順に再配置した結果: 4 10 3 5 7 12 22 24

このように、xの倍数となる要素だけを昘順に並べ替えながら、それ以外の要素は元の位置に保持できるため、計算量 O(N log N) のシンプルかつ効率的な実装となっています。