Reversal algorithm for array rotation written in C++

In the given problem, we have an array and we need to rotate the array by d elements using inversion algorithm, for example −

Input : arr[] = [1, 2, 3, 4, 5, 6, 7], d = 2
Output : arr[] = [3, 4, 5, 6, 7, 1, 2]
Explanation : As you can see we have to rotate this array by d = 2 but our main task is to achieve this by using a reversal technique.

We have an array The rotation was calculated with some inversion techniques and came to the conclusion:

• First, we invert the first d elements of the array.
• Second, we reverse the remaining elements.
• Third, we reverse the entire array.

By applying these three steps, we can get the rotated array.

Solution Method

In this problem, first, we are going to write a function that reverses the elements; now we follow the above steps.

Example

#include <bits/stdc++.h>
using namespace std;

void reverseArray(int arr[], int start, int end) { // our reversal algorithm
   while (start < end) { // if start becomes equal to end we break the loop
      int temp = arr[start];
      arr[start] = arr[end];
      arr[end] = temp;
      start++;
      end--;
   }
   return ;
}
void Rotate(int arr[], int d, int n) { // rotation function
   if (d == 0) // no rotation required
      return;
   d = d % n; // when d becomes equal to n so our array comes to its original form
   reverseArray(arr, 0, d - 1); // reversing first d elements
   reverseArray(arr, d, n - 1); // reversing the remaining elements
   reverseArray(arr, 0, n - 1); // reversing the whole array

   return ;
}
int main() {
   int arr[] = { 1, 2, 3, 4, 5, 6, 7 }; // given array
   int n = sizeof(arr) / sizeof(arr[0]); // size of our array
   int d = 2;
   Rotate(arr, d, n);
   for(int i = 0; i < n; i++) // printing the array
      cout << arr[i] << " ";
   cout << "\n";
   return 0;
}

Output

3 4 5 6 7 1 2

Explanation of the above code

In the above method, we first create an inversion technique that will accept three parameters, namely the array, starting index and ending index, and reverses our array from the starting position to the ending position. Since we have developed the algorithm previously, we will use this function to apply the algorithm. First, we reverse the first d elements. Then, we reverse the remaining elements, and finally, we reverse the entire array. As a result, our array is rotated by d positions. In the rotation function, we set d to d % n. This is because if we rotate the first n elements of the array, we will get the same answer as before, so we take d modulo n.

Conclusion

In this article, we solved a problem of applying the inversion algorithm for array rotation. We also learned the C program and the complete (normal) method to solve this problem. We can write the same program in other languages ​​like C, Java, Python and others. Hope this article is helpful to you.

The above is the detailed content of Reversal algorithm for array rotation written in C++. For more information, please follow other related articles on the PHP Chinese website!