C++で偶数を偶数インデックスへ、奇数を奇数インデックスへ並べ替える方法

この問題では、サイズnの配列arr[]が与えられます。配列は半分(n/2個)が偶数、残り半分(n/2個)が奇数で構成されており、偶数を偶数インデックス(0, 2, 4…)に、奇数を奇数インデックス(1, 3, 5…)に配置するプログラムを作成することが課題です。

問題を理解するための例

入力: arr[] = {5, 1, 6, 4, 3, 8}

出力: arr[] = {6, 1, 5, 4, 3, 8}

解決アプローチ

まず思いつくのは、配列を走査しながら「偶数位置にない値」を見つけ、次の奇数位置の値と入れ替えていく方法です。これは有効な解法ですが、偶数用と奇数用の2つのインデックスを使うことで、より効率的に処理できます。

具体的には、以下の手順で進めます。

• eIndex(偶数インデックス)は偶数番目の位置(0, 2, 4…)を追跡します。
• oIndex(奇数インデックス)は奇数番目の位置(1, 3, 5…)を追跡します。
• 偶数インデックスに偶数以外の要素があり、かつ奇数インデックスに奇数以外の要素が見つかった場合、その2つをスワップします。
• 条件を満たさない場合は、両方のインデックスを2ずつ進めて次の候補を探します。

この方法なら各要素を最大1回しかチェックしないため、時間計算量はO(n)、追加のメモリも不要で空間計算量はO(1)という非常に効率的なアルゴリズムになります。

解法の動作を示すプログラム

#include <iostream>
using namespace std;

void O_EReshuffle(int arr[], int n) {
    
    int oIndex = 1;
    int eIndex = 0;
    
    for(int i = 0; i < n; ) {
        
        while (eIndex < n && arr[eIndex] % 2 == 0)
            eIndex += 2;
            
        while (oIndex < n && arr[oIndex] % 2 == 1)
            oIndex += 2;
            
        if (eIndex < n && oIndex < n)
            swap (arr[eIndex], arr[oIndex]);
            
        else
            break;
    }
}

int main()
{
    int arr[] = { 5, 1, 6, 4, 3, 8 };
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "Array before Reshuffling: ";
    for(int i = 0; i < n ; i++){
        cout<<arr[i]<<"\t";
    }
    O_EReshuffle(arr, n);

    cout<<"\nArray after Reshuffling: ";
    for(int i = 0; i < n ; i++){
        cout<<arr[i]<<"\t";
    };

    return 0;
}

実行結果

Array before Reshuffling: 5 1 6 4 3 8
Array after Reshuffling: 4 1 6 5 8 3

実行結果からわかるように、並べ替え後の配列では偶数(4, 6, 8)が偶数インデックス(0, 2, 4)に、奇数(1, 5, 3)が奇数インデックス(1, 3, 5)に正しく配置されています。このように2つのインデックスを併用する手法は、余計な走査を省きながら条件を満たす配置を一度のループで実現できる、シンプルかつ高性能なアプローチです。