C++で配列がペアワイズソートされているかどうかを確認する方法

要素数 n の配列 A が与えられたとき、その配列が「ペアワイズソート（pairwise sorted）」されているかどうかを判定します。ペアワイズソートとは、隣接する2つの要素からなるペアごとに昇順に並んでいる状態を指します。

例えば、配列が {8, 10, 18, 20, 5, 15} の場合を考えてみましょう。この配列は (8, 10)、(18, 20)、(5, 15) という3つのペアに分けられます。それぞれのペア内で前の要素が後の要素以下になっているため、この配列はペアワイズソートされていると判断できます。

なお、配列の要素数が奇数の場合、最後の1つの要素はペアを形成できないため無視されます。

アルゴリズムの考え方

この問題へのアプローチは非常にシンプルです。インデックス i を 0 から始めて 2 ずつ増やしながらループし、各ステップで arr[i] が arr[i+1] 以下であるかどうかを確認します。もし arr[i] > arr[i+1] となるペアが見つかった時点で false を返し、すべてのペアが条件を満たしていれば true を返します。

計算量は O(n/2)、つまり O(n) となり、非常に効率的です。

実装例

#include <iostream>
#include <cmath>
using namespace std;

bool isPairwiseSorted(int arr[], int n) {
    if(n <= 1)
        return true;
    for(int i = 0; i<n; i += 2){
        if(arr[i] > arr[i + 1])
            return false;
    }
    return true;
}

int main() {
    int arr[] = {8, 10, 18, 20, 5, 15};
    int n = sizeof(arr)/sizeof(arr[0]);
    if(isPairwiseSorted(arr, n)){
        cout << "This is pairwise sorted";
    } else {
        cout << "This is not pairwise sorted";
    }
}

出力結果

This is pairwise sorted

ポイントのまとめ

• 要素数が 0 または 1 の場合は、ペアが存在しないため常に true を返します。
• ループ変数 i は 2 ずつ増加させることで、重なりなく各ペアを一度だけチェックできます。
• 奇数個の配列では最後の要素が自動的に無視されます（i+1 が範囲外になる前にループが終了するため）。