C++で配列を分割し、先頭部分を末尾に移動するプログラムの書き方

この記事では、配列を指定した位置で分割し、分割した先頭部分を配列の末尾に移動させる方法を解説します。例として、配列の内容が {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} である場合を考えます。この配列を2つの部分に分割します。1つ目の部分はインデックス0から3まで（分割サイズ4）、2つ目の部分は残りです。先頭部分を末尾に追加すると、配列は {4, 5, 6, 7, 8, 9, 0, 1, 2, 3} のようになります。

これは実質的に「左回転（left rotation）」と呼ばれる操作であり、先頭の要素を1つずつ取り出して末尾に移動する処理を、分割サイズ分だけ繰り返すことで実現できます。以下の手順で解決しましょう。

アルゴリズム

splitArray(arr, n, k)

引数はそれぞれ、arrが対象の配列、nが要素数、kが分割サイズを表します。

begin
    for i := 0 to k-1, do
        x := arr[0]           // 先頭の要素を保存
        for j := 0 to n-2, do
            arr[j] := arr[j+1] // 全要素を1つ左へずらす
        done
        arr[n-1] := x          // 保存した要素を末尾へ
    done
end

この処理をk回繰り返すことで、先頭のk個の要素が順番に末尾へと移動していきます。

サンプルコード

#include<iostream>
using namespace std;

void splitArray(int arr[], int n, int k){
    for(int i = 0; i<k; i++){
        int x = arr[0]; // 先頭の要素を一時的に保存
        for(int j = 0; j<= n-2; j++){
            arr[j] = arr[j+1]; // 各要素を1つ左にシフト
        }
        arr[n-1] = x; // 保存した要素を末尾に配置
    }
}

int main() {
    int data[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    int n = sizeof(data)/sizeof(data[0]);
    int i;
    cout << "Enter split size: ";
    cin >> i;
    splitArray(data, n, i);
    for(int j = 0; j <n; j++){
        cout << data[j] << " ";
    }
}

実行結果

Enter split size: 4
4 5 6 7 8 9 0 1 2 3

補足：計算量について

この手法は理解しやすい反面、時間計算量はO(n × k)となり、kが大きい場合は非効率になります。より効率化したい場合は、「ジグザグ反転法（Reversal Algorithm）」を使うとO(n)で同じ結果が得られます。また、std::rotate を使えば標準ライブラリだけで同様の操作が可能です。

#include <algorithm>
std::rotate(data, data + k, data + n); // 先頭k個を末尾へ回転

用途や規模に応じて、シンプルなループ方式と標準ライブラリ方式を使い分けるとよいでしょう。