C++での配列ローテーションのブロックスワップアルゴリズム

アレイローテーションのブロックスワップアルゴリズムは、アレイローテーションに使用される効率的なアルゴリズムです。 O（n）時間計算量で作業を行うことができます。

したがって、配列の回転では、サイズnの配列arr []と、番号を定義する数kが与えられます。回転する要素の。

配列の回転の例を見てみましょう-

入力 −

arr[] = {4, 6, 1, 8, 9, 2}, k = 2 (number of rotations.)

出力 −

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

説明 −回転時に、1つの要素を最後の位置にシフトし、次の要素を1つの位置にシフトします。

インデックス0の要素はインデックスn-1にシフトされます。そして、残りの要素は前のインデックスにシフトされます。

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

ブロックスワップアルゴリズムは、アレイのローテーションを完全に実行するために使用されます。

アルゴリズム

ステップ1 − kを除算点として、配列を2つのサブ配列で除算します。 X =arr [0...k-1]およびY=arr [k...n-1]とします。

ステップ2 − XとYのサイズが同じになるまで、以下の手順に従います。

ステップ2.1 − X> Yのサイズの場合、X1のサイズがYのサイズと等しくなるようにXを2つの部分X1とX2に分割します。次に、サブ配列X1とYを交換します。これにより、元の配列構成がX1X2YからYX2X1。

ステップ2.2 − Y> Xのサイズの場合、Y2のサイズがXのサイズと等しくなるようにYをY1とY2の2つの部分に分割します。次に、サブアレイXとY2を交換します。これにより、元のアレイ構成がXY1Y2からY2Y1Xに変更されます。

ステップ3 − XとYのサイズが同じ場合は、交換してください。

このアルゴリズムでは、同じコードチャンクを繰り返し呼び出す必要があります。この繰り返しの呼び出しは、2つのアプローチを使用して実現できます。それらは再帰的アプローチです および反復アプローチ 。プログラムを使用したアプローチについて説明します。

例

再帰的アプローチを説明するプログラム-

#include <iostream>
using namespace std;
void swapSubArray(int arr[], int start, int end, intk){
   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<<"Array before rotations :\t";
   for(int i = 0; i<size; i++)
      cout<<arr[i]<<" ";
   blockSwapAlgo(arr, k, size);
   cout<<"\nArray after rotating "<<k<<" times :\t";
   for(int i = 0; i<size; i++)
      cout<<arr[i]<<" ";
   return 0;
}

出力

Array before rotations : 4 6 1 8 9 2
Array after rotating 3 times : 8 9 2 4 6 1

例

反復アプローチを説明するプログラム-

#include <iostream>
using namespace std;
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<<"Array before rotations :\t";
   for(int i = 0; i<size; i++)
      cout<<arr[i]<<" ";
   blockSwapAlgoIt(arr, k, size);
   cout<<"\nArray after rotating "<<k<<" times :\t";
   for(int i = 0; i<size; i++)
      cout<<arr[i]<<" ";
   return 0;
}

出力

Array before rotations : 4 6 1 8 9 2
Array after rotating 3 times : 8 9 2 4 6 1