Juggling algorithm for array rotation C

Juggling-Algorithm for array rotation in C

Here in this program we’ll be learning about Juggling-Algorithm for array rotation in C. 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}

Juggling algorithm for array rotation C programming language
Juggling algorithm for array rotation C

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 :

    #include<stdio.h>

int gcd(int a, int b)
{
if(b==0)
return a;
else
return gcd(b, a%b);
}

void ArrayRotate (int A[], int n, int k)
{
int d=-1,i,temp,j;
for(i=0;i<gcd(n,k);i++)
{
j=i;
temp=A[i];
while(1)
{
d=(j+k)%n;
if(d==i)
break;
A[j]=A[d];
j=d;
}
A[j]=temp;
}
}

void displayArray(int A[],int n)
{
int i;
for(i=0;i<n;i++)
printf("%d ",A[i]);
printf("\n");
}

int main()
{
int n,i,k;
printf("Enter size of the Array\n");
scanf("%d",&n);
int A[n];
printf("Enter Array elements\n");
for(i=0;i<n;i++)
scanf("%d",&A[i]);
printf("Enter the value of k\n");
scanf("%d",&k);
displayArray(A,n);
ArrayRotate(A,n,k);
displayArray(A,n);
return 0;
}

Output: 

Enter size of the Array
5
Enter Array elements
1 2 3 4 5
Enter the value of k
2
1 2 3 4 5
3 4 5 1 2


Enter size of the Array
8
Enter Array elements
1
7
81
12
55
26
13
12
Enter the value of k
3
1 7 81 12 55 26 13 12
12 55 26 13 12 1 7 81