soorya54

Posted on

Array rotation by Reversal Algorithm

Array Rotation

Array Rotation simply means shifting the array elements to the left or right of the array by specified positions. An array can be rotated to the left(clockwise) or to the right (anti-clockwise) to the given number of positions.

Left rotation

Let's consider an array arr with n integer items stored in it. Let's assume d is the number of positions the array is to be rotated left, then the reversal algorithm can be applied as follows,

• Split the array into two parts A = arr[0...d-1] and B = arr[d...n-1]
• Reverse the array items of part A from position 0 to d-1
• Reverse the array items of part B from position d to n-1
• Now, reverse the entire resulting array to get the left rotated array
``````leftRotate(arr[], d, n)
arrayReverse(arr[], 0, d-1);
arrayReverse(arr[], d, n-1);
arrayReverse(arr[], 0, n-1);
``````

Let arr = {10, 20, 30, 40, 50, 60, 70, 80}, n = 8, d = 3

Code

``````#include <stdio.h>

// Using reversal algorithm
// T(n) = Θ(n)
// Aux space = Θ(1)

void reverse(int arr[], int low, int high) {
while(low < high) {
int tmp;

tmp = arr[low];
arr[low] = arr[high];
arr[high] = tmp;

low++;
high--;
}
}

void leftRotate(int arr[], int n, int d) {
reverse(arr, 0, d-1);
reverse(arr, d, n-1);
reverse(arr, 0, n-1);
}

int main() {
int arr[] = {10, 20, 30, 40, 50, 60, 70, 80};
int n = sizeof(arr)/sizeof(arr[0]);
leftRotate(arr, n, 3);

printf("Left rotated Array values are\n");
for(int l=0; l<n; l++)
printf("%d ", arr[l]);

return 0;
}
``````

Output

``````Left rotated Array values are
40 50 60 70 80 10 20 30
``````

Right rotation

In order to do right rotation of array items, the only change is first reverse the entire array and follow the reversal of subsets as shown below,

Code

``````void rightRotate(int arr[], int n, int d) {
reverse(arr, 0, n-1);
reverse(arr, 0, d-1);
reverse(arr, d, n-1);
}
``````

Output

``````Right rotated Array values are
60 70 80 10 20 30 40 50
``````