【C言語】配列の回転を実現する反転アルゴリズムの解説と実装

アルゴリズムとは、与えられた問題を解決するために順番に実行される一連の手順のことです。本記事では、配列の回転の中でも特に効率的な反転アルゴリズム（Reversal Algorithm）について詳しく解説し、実際にC言語でプログラムを作成します。

理解しておきたい基本用語

配列（Array）

配列とは、同じデータ型の複数の要素を格納するためのコンテナです。配列のサイズ（要素数）は、宣言時に固定されます。

配列の回転（Array Rotation）

配列の回転とは、配列内の要素の並び順をずらす操作のことです。たとえば左回転では、各要素のインデックスを1つ前へ移動させ、先頭の要素は末尾へ移動します。

配列の回転の例：

配列 arr[] = {3, 6, 8, 1, 4, 10}
左に2回転すると、
arr[] = {8, 1, 4, 10, 3, 6}

反転アルゴリズム（Reversal Algorithm）とは

反転アルゴリズムは、配列の回転を行う手法のひとつです。このアルゴリズムでは、配列をいくつかの部分配列に分割し、それぞれを個別に反転させたあと結合し、最後にもう一度全体を反転することで、回転後の配列を得ます。別途作業用の配列を用意する必要がなく、時間計算量 O(n)・追加メモリ O(1) で処理できる点が大きな特徴です。

アルゴリズムの手順

入力 : 配列 arr[] 、回転する位置の数 d 、配列の長さ n
ステップ1 : 配列を 0〜(d-1) と d〜(n-1) の2つの部分配列 a1[d]、a2[n-d] に分割する。
ステップ2 : reverse メソッドを使って、両方の部分配列をそれぞれ反転する。
ステップ3 : a1 と a2 を結合し、元のサイズの配列に戻す。
ステップ4 : 結合した配列全体を反転すると、回転後の配列が得られる。
ステップ5 : 標準出力を使って結果の配列を表示する。

具体例：

arr[] = {1, 4, 2, 8, 3, 6, 5}、d = 3、n = 7
a1[]  = {1, 4, 2}      // 前半の部分配列
a2[]  = {8, 3, 6, 5}   // 後半の部分配列
a1r[] = {2, 4, 1}      // a1 を反転
a2r[] = {5, 6, 3, 8}   // a2 を反転
ar[]  = {2, 4, 1, 5, 6, 3, 8}  // a1r + a2r を結合
arr[] = {8, 3, 6, 5, 1, 4, 2}  // 全体を反転 → 最終結果

C言語による実装例

#include <stdio.h>
void reverse(int arr[], int start, int end){
    int temp;
    while (start < end) {
        temp = arr[start];
        arr[start] = arr[end];
        arr[end] = temp;
        start++;
        end--;
    }
}
int main(){
    int arr[] = { 54, 67, 12, 76, 25, 16, 34 };
    int n = 7;
    int d = 2;
    printf("初期配列：\n");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    reverse(arr, 0, d - 1);
    reverse(arr, d, n - 1);
    reverse(arr, 0, n - 1);
    printf("\n%d 要素分左回転した後の配列：\n", d);
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    return 0;
}

実行結果

初期配列：
54 67 12 76 25 16 34
2 要素分左回転した後の配列：
12 76 25 16 34 54 67

まとめ

反転アルゴリズムは、「部分配列の反転 → 結合 → 全体の反転」というシンプルな3段階の操作で配列の回転を実現します。追加の配列を確保する必要がなく、時間計算量 O(n)、空間計算量 O(1) で動作するため、一時配列を使う方法などと比べて実用的で効率的なアプローチといえます。