DEV Community

loading...
Cover image for Array rotation by Reversal Algorithm

Array rotation by Reversal Algorithm

soorya54
Software Engineer
・2 min read

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);
Enter fullscreen mode Exit fullscreen mode

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

Alt Text

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;
}
Enter fullscreen mode Exit fullscreen mode

Output

Left rotated Array values are
40 50 60 70 80 10 20 30
Enter fullscreen mode Exit fullscreen mode

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,

Alt Text

Code

void rightRotate(int arr[], int n, int d) {
    reverse(arr, 0, n-1);
    reverse(arr, 0, d-1);
    reverse(arr, d, n-1);
}
Enter fullscreen mode Exit fullscreen mode

Output

Right rotated Array values are
60 70 80 10 20 30 40 50 
Enter fullscreen mode Exit fullscreen mode

Thanks for reading!

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

Follow me on twitter: @soorya_54

Discussion (0)