array rotation

As the term rotation signifies, array rotation means to rotate the elements of an array by given positions.

Consider the below array:

int a[7]={1,2,3,4,5,6,7};

The above array is rotated counter-clockwise(towards left) by 2 elements. After rotation, the array will be:

 int a[7]={3,4,5,6,7,1,2};

Visually, the process of counter clock-wise array rotation(rotated by say K elements) looks like:

  *Shift all elements after K-th element to the left by K positions.

  *Fill the K blank spaces at the end of the array by first K elements from the original array.

Note: The similar approach can also be applied for clockwise array rotation.

                                             Implementations

*Simple Method: The simplest way to rotate an array is to implement the above visually observed approach by using extra space.

   1)Store the first K elements in a temporary array say temp[].

   2)Shift all elements after K-th element to the left by K positions in the original array.

   3)Fill the K blank spaces at the end of the original array by the K elements from the temp array.

Say, arr[] = [1, 2, 3, 4, 5, 6, 7], K = 2
1) Store first K elements in a temp array
   temp[] = [1, 2]
2) Shift rest of the arr[]
   arr[] = [3, 4, 5, 6, 7, 6, 7]
3) Store back the M elements from temp
   arr[] = [3, 4, 5, 6, 7, 1, 2]

Time Complexity: O(N), where N is the number of elements in the array.

Auxiliary Space: O(M) where K is the number of places by which elements will be rotated.

*Another Method (Without extra space): We can also rotate an array by avoiding the use of temporary array. The idea is to rotate the array one by one K times.

leftRotate(arr[], d, n)
{
  For i = 0 to i < d
    Left rotate all elements of arr[] by one
}

To rotate an array by 1 position to the left:

1)Store the first element in a temporary variable say temp.

2)Left shift all elements after the first element by 1 position. That is, move arr[1] to arr[0], arr[2] to arr[1] and so on.

3)Initialize arr[N-1] with temp.

To rotate an array by K position to the left, repeat the above process K times.

Take the same example,

arr[] = [1, 2, 3, 4, 5, 6, 7], K = 2

Rotate arr[] one by one 2 times.

After 1st rotation: [2, 3, 4, 5, 6, 7, 1]
After 2nd rotation: [ 3, 4, 5, 6, 7, 1, 2]

Time Complexity: O(N*K), where N is the number of elements in the array and Kis the number of places by which elements will be rotated.

Auxiliary Space: O(1).

*Juggling Algorithm: This is an extension of the above method. 

In this method, divide the array into M sets, where M = GCD (n, k), and then rotate the elements in each set.

From the number of elements ( n ) of the array and number of rotations ( k ) to be made to the array, the GCD(n, k) number of blocks are made.

Then in each block, shifting will take place to the corresponding elements in the block.

After all the elements in all the blocks are shifted, the array will be rotated for the given number of times.

For Example: If we want to rotate the below array by 2 positions.

            1 2 3 4 5 6

      M = GCD(6, 2) = 2;

      Initial Array : 1  2  3  4  5  6   

      First Set Moves : 5   2   1   4   3   6

      Second Set Moves : 5   6   1   2   3   4          //  The array is rotated twice.

 

implementation in c++

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

/*Function to get gcd of a and b*/
int gcd(int a, int b) // gcd(a,b) number of blocks are formed
{
 if (b == 0)
 return a;
 else
 return gcd(b, a % b);
}

/*Function to left rotate array by n - number of rotations*/
void array_left_rotate(int arr[], int d, int n)
{
 int i, j, k, temp;
 for (i = 0; i < gcd(d, n); i++) // gcd(d,n) times the loop will iterate
 {

 /* move i-th values of blocks */
 temp = arr[i];
 j = i;
 while (1) {
 k = j + d;
 if (k >= n) // The element has to be shifted to its rotated position
 k = k - n;
 if (k == i) // The element is already in its rotated position
 break;
 arr[j] = arr[k];
 j = k;
 }
 arr[j] = temp;
 }}

int main()
{
 int arr[] = { 1, 2, 3, 4, 5, 6, 7 };
 int n = sizeof(arr) / sizeof(arr[0]); // Finding the size of the array
 cout<<"\nArray elements before rotating : \n";
 for(int i = 0; i < n; i++)
 {
 cout<<arr[i]<<"\t"; // Printing the array elements
 }
 int no_of_rotations = 2; // Number of rotations to take place
 array_left_rotate(arr, no_of_rotations, n);
 cout<<"\n\nArray elements after rotating : \n";
 for(int i = 0; i < n; i++)
 {
 cout<<arr[i]<<"\t"; // Printing the array elements after rotation of elements
 }
 cout<<"\n";
 return 0;
}

output:

Array elements before rotating:
1 2 3 4 5 6 7

Array elements after rotating:
2 3 4 5 6 7 1

Time Complexity: O(N), where N is the number of elements in the array.

Auxiliary Space: O(1).