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