【Java】反転アルゴリズムを使って配列を回転させるプログラムの書き方

配列の回転を実現する手法のひとつに、「反転アルゴリズム（Reversal Algorithm）」と呼ばれる効率的なアプローチがあります。このアルゴリズムでは、配列を3回部分反転するだけで、目的の回転結果を得ることができます。

具体的な手順は以下の通りです。

1. 回転させたい位置までの要素を反転する
2. 残りの要素を反転する
3. 配列全体を反転する

この方法なら、追加の配列を用意する必要がなく、時間計算量 O(n)、空間計算量 O(1) で処理できるのが大きな特徴です。

サンプルプログラム

以下は、反転アルゴリズムを使って配列を左回転させるJavaプログラムの例です。

import java.io.*;
public class Demo{
   static void rotate_left(int my_arr[], int no_of_rotation){
      int n = my_arr.length;
      array_reversal(my_arr, 0, no_of_rotation - 1);
      array_reversal(my_arr, no_of_rotation, n - 1);
      array_reversal(my_arr, 0, n - 1);
   }
   static void array_reversal(int my_arr[], int start, int end){
      int temp;
      while (start < end) {
         temp = my_arr[start];
         my_arr[start] = my_arr[end];
         my_arr[end] = temp;
         start++;
         end--;
      }
   }
   public static void main(String[] args){
      int my_arr[] = { 45, 67, 89, 91, 23, 0, 11 };
      rotate_left(my_arr, 4);
      System.out.println("The array after rotating is ");
      for (int i = 0; i < my_arr.length; i++)
      System.out.print(my_arr[i] + " ");
   }
}

実行結果

The array after rotating is
23 0 11 45 67 89 91

プログラムの解説

まず、Demo クラスの中に rotate_left メソッドが定義されています。このメソッドには、対象となる配列と、回転させる要素数がパラメータとして渡されます。メソッド内では、配列の長さを変数 n に格納した後、array_reversal メソッドを3回呼び出しています。

• 1回目：先頭から回転数の直前まで（0 ～ no_of_rotation - 1）を反転
• 2回目：回転数以降から末尾まで（no_of_rotation ～ n - 1）を反転
• 3回目：配列全体（0 ～ n - 1）を反転

次に、array_reversal メソッドは、配列・開始インデックス・終了インデックスの3つの引数を受け取ります。開始インデックスが終了インデックスより小さい間、一時変数 temp を使って両端の要素を交換していきます。交換のたびに開始インデックスを1つ増やし、終了インデックスを1つ減らすことで、指定範囲の要素が反転されます。

最後に、main メソッドで初期状態の配列を定義し、rotate_left メソッドを呼び出して4要素分の左回転を行っています。その後、forループを使って回転後の配列の内容をコンソールに出力します。

このように、反転アルゴリズムを活用すれば、シンプルなコードでありながら効率的に配列の回転処理を実装できます。