【C++】偶数番目の要素が奇数番目より大きくなるように配列を再配置する方法

正と負の整数を含む整数型配列 arr[] が与えられます。この課題では、配列を再配置して、偶数番目（インデックス）に位置するすべての要素が、奇数番目に位置する要素よりも常に大きくなるようにし、その結果を出力します。

入出力シナリオの確認

入力 − int arr[] = {2, 1, 4, 3, 6, 5, 8, 7}

出力 − 再配置前の配列: 2 1 4 3 6 5 8 7
偶数番目の要素が奇数番目より大きくなるように再配置した結果: 1 8 2 7 3 6 4 5

説明 − サイズ8の整数配列が与えられています。まず配列を昇順にソートし、その後、最小値側と最大値側から交互に要素を取り出して並べることで、偶数番目の要素が必ず隣接する奇数番目の要素より大きい配列「1 8 2 7 3 6 4 5」が得られます。

入力 − int arr[] = {-3, 2, -4, -1}

出力 − 再配置前の配列: -3 2 -4 -1
偶数番目の要素が奇数番目より大きくなるように再配置した結果: -4 2 -3 -1

説明 − サイズ4の整数配列に対して同じ手順を適用します。ソート後の「-4 -3 -1 2」から両端を交互に配置することで、「-4 2 -3 -1」という結果が得られます。

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

• 整数型の配列を入力として受け取り、配列のサイズを計算します。
• C++ STL の sort 関数に配列の先頭ポインタとサイズを渡して、配列を昇順にソートします。
• 関数 Rearrangement(arr, size) を呼び出して再配置を行います。
• 関数 Rearrangement(arr, size) の内部処理は以下の通りです。
  • 元の配列 arr[size] と同じサイズの一時配列 ptr[size] を用意します。
  • 一時変数 first を 0、last を size - 1 で初期化します。
  • i を 0 から配列サイズ未満まで繰り返す FOR ループを開始します。ループ内で (i + 1) % 2 == 0（偶数番目）の場合は ptr[i] に arr[last--]（残りの最大値）を代入し、それ以外の場合は ptr[i] に arr[first++]（残りの最小値）を代入します。
  • ループ終了後、並べ替えた ptr の内容を元の配列 arr にコピーして反映させます。
• 結果を出力します。

この手法では、ソート済み配列の小さい方から奇数番目へ、大きい方から偶数番目へ交互に配置していくため、すべての偶数番目の要素が直前の奇数番目の要素より確実に大きくなります。計算量はソート部分が支配的であり、時間計算量は O(n log n)、追加で必要な空間計算量は O(n) となります。

例

#include <bits/stdc++.h>
using namespace std;
void Rearrangement(int* arr, int size){
    int* ptr = new int[size];
    int first = 0;
    int last = size - 1;
    for (int i = 0; i < size; i++){
       if((i + 1) % 2 == 0){
          ptr[i] = arr[last--];
       }
       else{
          ptr[i] = arr[first++];
       }
    }
    // 並べ替えた結果を元の配列に戻す
    for (int i = 0; i < size; i++){
       arr[i] = ptr[i];
    }
    delete[] ptr;
}
int main(){
    // 配列の入力
    int arr[] = {2, 1, 4, 3, 6, 5, 8, 7};
    int size = sizeof(arr) / sizeof(arr[0]);
    // 元の配列を表示
    cout<<"Array before Arrangement: ";
    for (int i = 0; i < size; i++){
       cout << arr[i] << " ";
    }
    // 配列をソート
    sort(arr, arr + size);
    // 再配置関数を呼び出し
    Rearrangement(arr, size);
    // 再配置後の配列を表示
    cout<<"\nRearrangement of an array such that even positioned are greater than odd is: ";
    for(int i = 0; i < size; i++){
       cout<< arr[i] << " ";
    }
    return 0;
}

出力

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

Array before Arrangement: 2 1 4 3 6 5 8 7
Rearrangement of an array such that even positioned are greater than odd is: 1 8 2 7 3 6 4 5