C ++中用于数组旋转的块交换算法

数组旋转的块交换算法是用于数组旋转的高效算法。它可以以O(n)的时间复杂度完成您的工作。

因此，在数组旋转中，我们得到了大小为n的数组arr []和定义为no的数字k。旋转元素的数量。

让我们看一个数组旋转的例子-

输入 -

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

输出-

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

解释-旋转时，我们将一个元素移到最后一个位置，然后将下一个元素移到一个位置。

索引为0的元素将移至索引n-1。其余元素将移至上一个索引。

块交换算法

块交换算法用于完美执行数组旋转。

算法

步骤1-将数组除以k为分割点的两个子数组。令它们为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的大小相同时，交换它们。

该算法需要重复调用相同的代码块。可以使用两种方法来实现此重复呼叫。它们是递归方法和迭代方法。我们将使用程序讨论该方法。

示例

程序来说明递归方法-

#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