C++ Program to find juggling algorithm for array rotation

Juggling-Algorithm for array rotation

 

Here in this program we’ll be learning about Juggling Algorithm. Juggling-algorithm is one of the efficient algorithms used for array rotation. Now, let’s discuss about juggling-algorithm and a program to rotate an array using the juggling-algorithm.

Example: Arr: {10 ,20 ,30 ,40 ,50 ,60}

                  After juggling anticlockwise

                  Arr : {50, 60, 10, 20, 30, 40}

C++ program to find juggling algorithm for array rotation

Algorithm :

  • 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.
  • Example: If we want to rotate the array Arr : {10, 20, 30, 40, 50, 60} by 2 positions :
  •  M = GCD(60, 20) = 20
  • Initial Array : 10  20  30  40  50  60  
  • First Set Moves : 50  20  10  40  30  60
  • Second Set Moves : 50   60  10  20  30  40    

 

C++ Program Based on above approach :

// C++ program to rotate an array by
// d elements
#include <bits/stdc++.h>
using namespace std;


/*Function to get gcd of a and b*/
int gcd (int a, int b)
{
if (b == 0)
return a;

else
return gcd (b, a % b);
}



/*Function to left rotate arr[] of siz n by d*/
void leftRotate (int arr[], int d, int n)
{

/* To handle if d >= n */
d = d % n;

int g_c_d = gcd (d, n);

for (int i = 0; i < g_c_d; i++)
{
/* move i-th values of blocks */
int temp = arr[i];

int j = i;

while (1)
{
int k = j + d;

if (k >= n)
k = k - n;

if (k == i)
break;

arr[j] = arr[k];
j = k;
}

arr[j] = temp;
}
}

/* Driver program to test above functions */
int main ()
{
int arr[] = { 10, 20, 30, 40, 50, 60 };

// Function calling
leftRotate (arr, 2, 7);

cout << "Array after two rotation : ";

for (int i = 0; i < 7; i++)
cout << arr[i] << " ";

return 0;

}

Output: 

Array after two rotation : 30 40 50 60 10 20