Juggling Algorithm

Question

METHOD (A Juggling Algorithm) Divide the array in different sets where number of sets is equal to GCD of n and d and move the elements within sets. If GCD is 1 as is for the above example array (n = 7 and d =2), then elements will be moved within one set only, we just start with temp = arr[0] and keep moving arr[I+d] to arr[I] and finally store temp at the right place.

Here is an example for n =12 and d = 3. GCD is 3 and

Let arr[] be {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}

a) Elements are first moved in first set – (See below diagram for this movement)

ArrayRotation

      arr[] after this step --> {4 2 3 7 5 6 10 8 9 1 11 12}

b) Then in second set. arr[] after this step --> {4 5 3 7 8 6 10 11 9 1 2 12}

c) Finally in third set. arr[] after this step --> {4 5 6 7 8 9 10 11 12 1 2 3} /* function to print an array */ void printArray(int arr[], int size);

/*Function to get gcd of a and b*/
int gcd(int a,int b);

/*Function to left rotate arr[] of siz n by d*/
void leftRotate(int arr[], int d, int n)
{
  int i, j, k, temp;
  for (i = 0; i < gcd(d, n); i++)
  {
    /* move i-th values of blocks */
    temp = arr[i];
    j = i;
    while(1)
    {
      k = j + d;
      if (k >= n)
        k = k - n;
      if (k == i)
        break;
      arr[j] = arr[k];
      j = k;
    }
    arr[j] = temp;
  }
}

/*UTILITY FUNCTIONS*/
/* function to print an array */
void printArray(int arr[], int size)
{
  int i;
  for(i = 0; i < size; i++)
    printf("%d ", arr[i]);
}

/*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);
}

/* Driver program to test above functions */
int main()
{
   int arr[] = {1, 2, 3, 4, 5, 6, 7};
   leftRotate(arr, 2, 7);
   printArray(arr, 7);
   getchar();
   return 0;
}

Time complexity: O(n) Auxiliary Space: O(1)

Can somebody please give me nice explanation of how this algorithm works and its asymptotic complexity?

Orren

Answer 1

The for loop in the function:

leftRotate(int arr[], int d, int n)

is going to make exatcly gcd(d, n) iterations. Now lets look at what is happening inside the loop: it takes all the cells arr[k]which fulfill: k % gcd(d, n) == i and swaps them. Of course there are exactly: n / gcd(d, n) of them and that is how many swaps the function will make in one iteration of the loop. Therefore the whole asymptotic time complexity of the function is going to be O(gcd(d, n) * n / gcd(d, n)) == O(n). The rest of the code does not have an impact on the time complexity and is pretty much self explainatory.

Cahier

Answer 2

Juggling 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.

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.

public class Main
{

/*Fuction to get gcd of a and b*/
public static int gcd(int a, int b) 
{ 
    if (b == 0) 
        return a; 
    else
        return gcd(b, a % b); 
}

/*Function to left rotate array of by d number of rotations*/
public static void leftRotate(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 (true) { 
            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; 
    }} 

//  Main function
public static void main(String[] args) 
{ 
    int arr[] = { 1, 2, 3, 4, 5, 6, 7 }; 
    int no_of_rotations = 2;
    int n = arr.length;
    System.out.println("Array Elements before rotating : "); 
    for(int i = 0 ; i < n ; i++)
    {
        System.out.print(arr[i]+ " "); // Printing elements before rotation
    }
    leftRotate(arr, no_of_rotations, n); 
    System.out.println("\nArray Elements after rotating : "); 
    for(int i = 0 ; i < n ; i++)
    {
        System.out.print(arr[i] + " "); // Printing elements after rotation
} } }

Maybellemayberry