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 

Thanks for reading!

If you have any questions about the post feel free to leave a comment below.

Follow me on twitter: @soorya_54