C++で偶数インデックスの要素が小さく、奇数インデックスの要素が大きくなるように配列を再配置する方法

正と負の両方の数値を含む整数型配列 arr[] が任意のサイズで与えられます。この課題では、偶数番目のインデックスにあるすべての要素が、隣接する奇数番目のインデックスの要素よりも小さくなるように配列を再配置し、その結果を出力することが求められます。

このような並びは「波状（ウェーブ）パターン」とも呼ばれ、1回の走査で O(n) の計算量を実現できる効率的な手法として知られています。

入出力シナリオの例

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

出力 − 整理前の配列：2 1 4 3 6 5 8 7
偶数インデックスの要素が小さく、奇数インデックスの要素が大きくなるように再配置した結果：1 4 2 6 3 8 5 7

説明 − 正と負の要素を含むサイズ8の整数配列が与えられています。ここで、偶数番目の位置にあるすべての要素が奇数番目の位置の要素より小さくなるように配列を再配置すると、結果は「1 4 2 6 3 8 5 7」となります。

入力 − int arr[] = {10, -1, 7, -5, 6, -9}

出力 − 整理前の配列：10 -1 7 -5 6 -9
偶数インデックスの要素が小さく、奇数インデックスの要素が大きくなるように再配置した結果：-1 10 -5 7 -9 6

説明 − 正と負の要素を含むサイズ6の整数配列が与えられています。同様に、偶数番目の位置の要素が奇数番目の位置の要素より小さくなるように再配置すると、結果は「-1 10 -5 7 -9 6」となります。

プログラムで使用しているアプローチ

• 整数型の要素からなる配列を入力し、配列のサイズを計算します。

• FORループを使用して、再配置を行う前の配列の内容を出力します。

• 配列とそのサイズを引数として渡し、関数 Rearrangement(arr, size) を呼び出します。

• 関数 Rearrangement(arr, size) の内部では以下の処理を行います。

  • i を0から size - 1 未満までループさせます。ループ内で i % 2 == 0 の場合（偶数インデックス）、arr[i] が arr[i + 1] より大きければ、C++ STL の swap メソッドを使って arr[i] と arr[i + 1] を入れ替えます。

  • 次に、i % 2 != 0 の場合（奇数インデックス）、arr[i] が arr[i + 1] より小さければ、STL の swap メソッドを使って arr[i] と arr[i + 1] を入れ替えます。

この処理により、配列を左から右へ一度だけ走査しながら条件に応じて隣接要素を交換していくため、時間計算量は O(n)、追加のメモリ使用量は O(1) で済みます。

コード例

#include <iostream>
using namespace std;
void Rearrangement(int* arr, int size){
    for(int i = 0; i < size - 1; i++){
        if(i % 2 == 0 ){
            if(arr[i] > arr[i + 1]){
                swap(arr[i], arr[i + 1]);
            }
        }
        if(i % 2 != 0){
            if(arr[i] < arr[i + 1]){
                swap(arr[i], arr[i + 1]);
            }
        }
    }
}
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] << " ";
    }
    // 配列を再配置する関数を呼び出し
    Rearrangement(arr, size);
    // 再配置後の配列を出力
    cout<<"\nRearrangement of an array such that even index elements are smaller and odd index elements are greater 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 index elements are smaller and odd index elements are greater is: 1 4 2 6 3 8 5 7