【C++】奇数インデックスの要素が前の要素より大きくなるように配列を再配置する方法

正の整数型の配列 arr[] が与えられます。この記事では、奇数インデックスに存在するすべての要素が、直前の偶数インデックスの要素よりも大きくなるように配列を再配置し、その結果を出力する方法を解説します。

入出力シナリオの例

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

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

説明 − サイズ7の整数配列が与えられています。偶数インデックスの要素の方が大きい場合には、偶数インデックスの要素と奇数インデックスの要素を交換（スワップ）していきます。

Arr[0] > arr[1] → swap実行 → {1, 2, 5, 4, 3, 7, 8}
Arr[2] > arr[3] → swap実行 → {1, 2, 4, 5, 3, 7, 8}
Arr[6] > arr[5] → swap実行 → {1, 2, 4, 5, 3, 8, 7}
Arr[2] > arr[1] → swap実行 → {1, 4, 2, 5, 3, 8, 7}

入力 − int arr[] = {3, 2, 6, 9}

出力 −
整列前の配列： 3 2 6 9
奇数インデックスの要素がすべて前の要素より大きくなるように再配置した結果： 2 3 6 9

説明 − サイズ4の整数配列が与えられています。Arr[0] > arr[1] が成り立つため、swapを実行して {2, 3, 6, 9} となります。以降はすべての要素が条件を満たしているため、追加のスワップは不要です。

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

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

• 整列前の配列を出力し、関数 Rearrangement(arr, size) を呼び出します。

• 関数 Rearrangement(arr, size) の内部処理は以下の通りです。

  • 整数型の変数 ptr を作成し、size - 1 で初期化します。

  • i を 0 から開始し、i が ptr 未満の間、i を 2 ずつ増加させながらループを実行します。ループ内で arr[i] > arr[i+1] が成り立つ場合は、swap(arr[i], arr[i+1]) を呼び出します。

  • size & 1（配列サイズが奇数）の場合、i を ptr から開始し、i が 0 より大きい間、i を 2 ずつ減少させながらループを実行します。ループ内で arr[i] > arr[i-1] が成り立つ場合は、swap(arr[i], arr[i-1]) を呼び出します。

• 再配置後の配列を出力します。

このアルゴリズムは配列を一度走査するだけで完結するため、時間計算量は O(n)、追加のメモリも不要（O(1)）という非常に効率的な手法です。

コード例

#include <iostream>
using namespace std;
void Rearrangement(int arr[], int size){
    int ptr = size - 1;
    for(int i = 0; i < ptr; i = i+2){
        if(arr[i] > arr[i+1]){
            swap(arr[i], arr[i+1]);
        }
    }
    if(size & 1){
        for(int i = ptr; i > 0; i = i-2){
            if(arr[i] > arr[i-1]){
                swap(arr[i], arr[i-1]);
            }
        }
    }
}
int main(){
    // 配列の入力
    int arr[] = {2, 1, 5, 4, 3, 7, 8};
    int size = sizeof(arr) / sizeof(arr[0]);
    // 元の配列を出力
    cout << "整列前の配列: ";
    for (int i = 0; i < size; i++){
        cout << arr[i] << " ";
    }
    // 配列を再配置する関数を呼び出し
    Rearrangement(arr, size);
    // 再配置後の配列を出力
    cout << "\n奇数インデックスの要素が前の要素より大きくなるように再配置した結果: ";
    for(int i = 0; i < size; i++){
        cout << arr[i] << " ";
    }
    return 0;
}

出力

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

整列前の配列: 2 1 5 4 3 7 8
奇数インデックスの要素が前の要素より大きくなるように再配置した結果: 1 4 2 5 3 8 7