C++でKの倍数間にある配列要素をソートする方法

配列Aと整数Kが与えられたとき、Kの倍数と次の倍数の「間」に挟まれた要素だけをソートすることを考えます。例えば、配列Aが [2, 13, 3, 1, 21, 7, 8, 13, 12]、K = 2 の場合、期待される出力は [2, 1, 3, 7, 13, 21, 8, 13, 12] です。
ここで2の倍数は 2・8・12 の3つです。最初の倍数2と次の倍数8の間にある 13, 3, 1, 21, 7 は昇順に並べ替えて 1, 3, 7, 13, 21 とし、8と12の間には要素13しかないため、すでに整列済みとしてそのまま残します。

アルゴリズムの考え方

配列を先頭から順に走査し、Kの倍数に該当する要素の位置（インデックス）を記録していきます。そして、2つ目以降のKの倍数が見つかるたびに、「直前に見つけた倍数の位置」と「現在の倍数の位置」の間にある要素を std::sort で昇順ソートします。Kの倍数そのものは動かさず、あくまで倍数と倍数の間の要素だけを対象にするのがポイントです。

処理の手順

1. 直前のKの倍数のインデックスを保持する変数 prev_index を -1 で初期化します。
2. 配列を走査し、arr[i] % K == 0 となる要素（Kの倍数）を探します。
3. 見つかった要素が最初の倍数でない場合（prev_index != -1）、範囲 [prev_index + 1, i) をソートします。
4. 現在のインデックス i を prev_index に更新して走査を続けます。

C++での実装例

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

void display(int arr[], int n) {
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
}

void sortBetweenMultipleOfK(int arr[], int n, int k) {
    int prev_index = -1;
    for (int i = 0; i < n; i++) {
        if (arr[i] % k == 0) {
            if (prev_index != -1) // 最初のKの倍数ではないことを確認
                sort(arr + prev_index + 1, arr + i);
            prev_index = i;
        }
    }
}

int main() {
    int arr[] = {2, 13, 3, 1, 21, 7, 8, 13, 12};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 2;
    cout << "Before Sort: "; display(arr, n);
    sortBetweenMultipleOfK(arr, n, k);
    cout << "\nAfter Sort : "; display(arr, n);
}

実行結果

Before Sort: 2 13 3 1 21 7 8 13 12
After Sort : 2 1 3 7 13 21 8 13 12

計算量

時間計算量： 各セグメントのソートには O(m log m)（m はセグメントの長さ）が必要ですが、全体としては O(n log n) に収まります。
空間計算量： std::sort はインプレースで動作するため、追加の補助メモリはほぼ不要（O(1)）です。