C++で偶数インデックスの要素は前方の全要素以下、奇数インデックスの要素は前方の全要素以上となるように配列を再配置する方法

問題の概要

奇数と偶数の整数値が混在する整数型配列が与えられます。この配列を、インデックスの偶奇に応じて次の条件を満たすように並べ替えることが課題です。

• インデックス i が偶数のとき：arr[i] <= arr[j](j < i を満たすすべての j に対して)。つまり、その位置の要素は自分より前にある全要素以下になります。
• インデックス i が奇数のとき：arr[i] >= arr[j](j < i を満たすすべての j に対して)。つまり、その位置の要素は自分より前にある全要素以上になります。

結果として、配列は「小さい値・大きい値」が交互に並ぶジグザグ状のパターンへと再配置されます。

入出力例

例1

入力： int arr[] = {5, 9, 10, 12, 32, 35, 67, 89}

出力： 再配置後の配列：12 32 10 35 9 67 5 89

説明： 与えられた配列には奇数と偶数の整数が混在しています。ソート済みの値をもとに、偶数インデックスには小さい方の値を降順で、奇数インデックスには大きい方の値を昇順で割り当てると、上記の出力が得られます。例えば、インデックス2(偶数)の「10」はそれ以前の要素(12, 32)すべて以下であり、インデックス3(奇数)の「35」はそれ以前の要素(12, 32, 10)すべて以上となり、条件を満たしています。

例2

入力： int arr[] = {4, 5, 1, 2, 9, 10}

出力： 再配置後の配列：4 5 2 9 1 10

説明： 同様に、偶数インデックス(0, 2, 4)には昇順ソートした配列の先頭側から小さい値が、奇数インデックス(1, 3, 5)には残りの大きい値が順に配置され、条件を満たす並びになります。

アルゴリズムの手順

このプログラムで採用しているアプローチは以下の通りです。

1. 整数型の配列を宣言し、size = sizeof(arr) / sizeof(arr[0]) によって要素数を求めます。
2. 関数 array_rearrange(arr, size) を呼び出し、配列とサイズを引数として渡します。
   1. 変数 even を size / 2(偶数インデックスの個数)、変数 odd を size - even(奇数インデックスの個数)として初期化します。
   2. 変数 temp を odd - 1 で初期化し、元の配列と同じサイズの作業用配列 arr_2[] を用意します。
   3. for ループを使って、arr の全要素を arr_2 にコピーします。
   4. sort(arr_2, arr_2 + size) を呼び出して、arr_2 を昇順にソートします。
   5. i を 0 から 2 ずつ増やしながら(size 未満の間)、arr[i] に arr_2[temp] を代入し、temp を 1 減らします。これにより、偶数インデックスにはソート済み配列の小さい方の値が降順で格納されます。
   6. temp を odd に戻し、今度は i を 1 から 2 ずつ増やしながら、arr[i] に arr_2[temp] を代入して temp を 1 増やします。これにより、奇数インデックスには残りの大きい値が昇順で格納されます。
   7. 最後に、for ループで再配置後の arr の全要素を出力します。

C++での実装例

#include <bits/stdc++.h>

using namespace std;
void array_rearrange(int arr[], int size){
    int even = size / 2;
    int odd = size - even;
    int temp = odd - 1;
    int arr_2[size];
    for(int i = 0; i < size; i++){
        arr_2[i] = arr[i];
    }
    sort(arr_2, arr_2 + size);
    for(int i = 0; i < size; i += 2){
        arr[i] = arr_2[temp];
        temp--;
    }
    temp = odd;
    for(int i = 1; i < size; i += 2){
        arr[i] = arr_2[temp];
        temp++;
    }
    cout<<"Array after rearranging elements are: ";
    for (int i = 0; i < size; i++){
        cout << arr[i] << " ";
    }
}
int main(){
    int arr[] = {5, 9, 10, 12, 32, 35, 67, 89};
    int size = sizeof(arr) / sizeof(arr[0]);
    array_rearrange(arr, size);
    return 0;
}

実行結果

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

Array after rearranging elements are: 12 32 10 35 9 67 5 89

計算量

このアルゴリズムの時間計算量は、ソート処理が支配的となるため O(n log n) です。また、元の配列を作業用配列 arr_2 にコピーしているため、必要な補助空間の計算量は O(n) となります。