C++での配列回転をO(n)で実現！ブロックスワップアルゴリズムの解説

ブロックスワップアルゴリズム（Block Swap Algorithm）は、配列の回転（ローテーション）を効率的に実行するためのアルゴリズムです。最大の特徴は、O(n) の時間計算量で処理を完了できる点にあります。

配列の回転では、サイズ n の配列 arr[] と、先頭から回転する要素数を指定する整数 k が与えられます。

配列回転の具体例

入力：

arr[] = {4, 6, 1, 8, 9, 2}, k = 2（回転する要素数）

出力：

{1, 8, 9, 2, 4, 6}

解説： 回転では、先頭の要素を末尾へ移動させ、残りの要素を1つずつ前方へずらします。つまり、インデックス0の要素はインデックス n-1 へ移動し、その他の要素はすべて1つ前のインデックスへシフトされます。

ブロックスワップアルゴリズムとは

ブロックスワップアルゴリズムは、配列を2つのブロック（部分配列）に分割し、それらを入れ替える操作を繰り返すことで、余分なメモリを使わずに配列の回転を正確に実現する手法です。

アルゴリズムの手順

ステップ1： 分割点 k を基準に、配列を2つの部分配列に分割します。X = arr[0...k-1]、Y = arr[k...n-1] とします。

ステップ2： X と Y のサイズが等しくなるまで、以下の処理を繰り返します。

ステップ2.1： X のサイズが Y より大きい場合、X を X1 と X2 に分割します（X1 のサイズ＝Y のサイズ）。その後、部分配列 X1 と Y を入れ替えます。これにより、配列の構成は X1X2Y から YX2X1 へと変化します。

ステップ2.2： Y のサイズが X より大きい場合、Y を Y1 と Y2 に分割します（Y2 のサイズ＝X のサイズ）。その後、部分配列 X と Y2 を入れ替えます。これにより、配列の構成は XY1Y2 から Y2Y1X へと変化します。

ステップ3： X と Y のサイズが等しくなったら、両方を入れ替えて完了です。

このアルゴリズムでは、同じ一連のコードを繰り返し呼び出す必要があります。この繰り返しは、再帰的アプローチと反復的アプローチという2つの方法で実装できます。以下では、実際のプログラムを通じてそれぞれの方法を紹介します。

実装例：再帰的アプローチ

#include <iostream>
using namespace std;

// start番目からk個の要素と、end番目からk個の要素を入れ替える
void swapSubArray(int arr[], int start, int end, int k){
    int temp;
    for(int i = 0; i < k; i++){
        temp = arr[start + i];
        arr[start + i] = arr[end + i];
        arr[end + i] = temp;
    }
}

// ブロックスワップによる配列回転（再帰版）
void blockSwapAlgo(int arr[], int k, int n) {
    if(k == 0 || k == n)
        return;
    if(k < (n-k)) {
        swapSubArray(arr, 0, (n-k), k);
        blockSwapAlgo(arr, k, (n-k));
    }
    else if(k > (n-k)){
        swapSubArray(arr, 0, k, (n-k));
        blockSwapAlgo((arr+n-k), (2*k-n), k);
    }
    else{
        swapSubArray(arr, 0, (n-k), k);
        return;
    }
}

int main() {
    int arr[] = {4, 6, 1, 8, 9, 2};
    int size = sizeof(arr) / sizeof(arr[0]);
    int k = 3;
    cout<<"回転前の配列 :\t";
    for(int i = 0; i<size; i++)
        cout<<arr[i]<<" ";
    blockSwapAlgo(arr, k, size);
    cout<<"\n"<<k<<"個分回転した後の配列 :\t";
    for(int i = 0; i<size; i++)
        cout<<arr[i]<<" ";
    return 0;
}

出力結果

回転前の配列 : 4 6 1 8 9 2
3個分回転した後の配列 : 8 9 2 4 6 1

実装例：反復的アプローチ

#include <iostream>
using namespace std;

// start番目からk個の要素と、end番目からk個の要素を入れ替える
void swapSubArray(int arr[], int start, int end, int k){
    int temp;
    for(int i = 0; i < k; i++){
        temp = arr[start + i];
        arr[start + i] = arr[end + i];
        arr[end + i] = temp;
    }
}

// ブロックスワップによる配列回転（反復版）
void blockSwapAlgoIt(int arr[], int k, int size) {
    int i, j;
    if(k == 0 || k == size)
        return;
    i = k;
    j = size - k;
    while (i != j) {
        if(i < j){
            swapSubArray(arr, k-i, k+j-i, i);
            j -= i;
        }
        else{
            swapSubArray(arr, k-i, k, j);
            i -= j;
        }
    }
    swapSubArray(arr, k-i, k, i);
}

int main() {
    int arr[] = {4, 6, 1, 8, 9, 2};
    int size = sizeof(arr) / sizeof(arr[0]);
    int k = 3;
    cout<<"回転前の配列 :\t";
    for(int i = 0; i<size; i++)
        cout<<arr[i]<<" ";
    blockSwapAlgoIt(arr, k, size);
    cout<<"\n"<<k<<"個分回転した後の配列 :\t";
    for(int i = 0; i<size; i++)
        cout<<arr[i]<<" ";
    return 0;
}

出力結果

回転前の配列 : 4 6 1 8 9 2
3個分回転した後の配列 : 8 9 2 4 6 1

計算量とまとめ

ブロックスワップアルゴリズムの計算量は以下のとおりです。

• 時間計算量： O(n) — 各要素が定数回のスワップで移動するため、配列全体でも線形時間で処理が完了します。
• 空間計算量： O(1) — 補助配列を必要とせず、その場（in-place）で回転できます。

このように、ブロックスワップアルゴリズムは追加メモリをほとんど使わずに高速な配列回転を実現できるため、組み込みシステムやメモリ制約の厳しい環境で特に有効な手法です。