Juggling Algorithm For Array Rotation In C++

The Juggling Algorithm presents a valuable technique in C++ for performing rotations through element shifting within an array. This approach involves segmenting the array into subsets based on the Greatest Common Divisor (GCD) of the array's size n and the number of positions d to be rotated. Subsequently, the elements undergo cyclic shifts to rotate each subset independently. This method guarantees complete movement of elements without requiring additional storage. With the array size denoted as n, the time complexity of this algorithm is O(n), while the space complexity is O(1). Particularly in scenarios involving extensive arrays and constrained memory resources, the Juggling Algorithm emerges as a highly practical solution for in-place rotations.

Key Concept of Juggling Algorithm:

The Juggling Algorithm is derived from two key factors: the Greatest Common Divisor (GCD) of the array's length n and the number of positions to rotate, d. Its application involves dividing the array into segments for rotation, with the GCD of n and d determining the number of sets calculated.

Juggling Algorithms Steps:

• ✅ GCD Calculation: In order to calculate GCD, it is necessary to find the GCD of n, the size of the array, and d, the number of rotations.
• ✅ Divide the Array to Create Sets: It is possible to think of all the elements in the array as components of cycles. For n and d, the GCD is the total number of sets. During the juggling process, each group of components is moved within the array.
• ✅ Rotate Elements in Sets: Take one element at a time from each set, relocate it to a new location and repeat the process until we have covered all possible regions.

If an array of length n undergoes rotation by a distance of d places, the number of distinct cycles that emerge can be determined as follows:

An array with a length of n, which has been rotated by d positions, exhibits an equivalent number of distinct cycles, each having a greatest common divisor (gcd) of n and d. These cycles originate from the initial position and progress by increments of d due to the rotational movement of the array. Consequently, the total distance covered within each cycle will be a multiple of n, specifically the least common multiple (lcm) of n and d. As a result, the quantity of elements contained in each cycle is precisely equal to lcm(n, d) divided by d. The total count of cycles necessary to encompass all n elements will be n divided by lcm(n, d), which simplifies to gcd(n, d).

Example:

To rotate an array containing seven elements, [1, 2, 3, 4, 5, 6, 7], by a value of d = 2, the following steps can be followed:

• ✅ Initially, determine the Greatest Common Divisor (GCD) of 7 and 2, which equals 1.
• ✅ The initial action involves relocating the first element of the rotated array to its correct position, followed by iterating through subsequent elements to complete a full cycle within the array.

Example:

Let's consider a scenario to demonstrate the Juggling Algorithm or array rotation in C++.

#include <iostream>
using namespace std;

// Function to get the GCD of two numbers
int gcd(int a, int b) {
    if (b == 0)
        return a;
    else
        return gcd(b, a % b);
}

// Function to rotate array by d positions using Juggling Algorithm
void rotateArray(int arr[], int n, int d) {
    // Reduce d if it's greater than n
    d = d % n;
    int g_c_d = gcd(d, n);
    
    // Rotate elements in sets
    for (int i = 0; i < g_c_d; i++) {
        int temp = arr[i];
        int j = i;
        
        while (true) {
            int k = j + d;
            if (k >= n) 
                k = k - n;
            if (k == i) 
                break;
            arr[j] = arr[k];
            j = k;
        }
        arr[j] = temp;
    }
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

int main() {
    int arr[] = {1, 2, 3, 4, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    int d = 2;
    
    rotateArray(arr, n, d);
    printArray(arr, n);
    
    return 0;
}

Output:

3 4 5 6 7 1 2

Explanation:

• ✅ The gcd function is also useful in determining the maximum number of times, the array has to be rotated by providing the maximum number of rotating sets, which is extracted using the gcd function.
• ✅ In the RotateArray function, the angular rotation of an object vector and matrix is performed manipulations in their own plane from coordinate to coordinate in this case, the parts are content moved in planes cyclically to perform angular shifting of the parts from the required d position.
• ✅ As stated above the time complexity is O(n) concerning the number of items in the array denoted by n.
• ✅ Only variables are involved in the process so the space complexity is constant thus O(1).

Conclusion:

In summary, the Juggling Algorithm stands out as the most efficient method for rotating an array as it enables in-place rotation with minimal memory usage. This approach is especially beneficial for shifting objects with minimal register shifting, achieved by calculating the total block shifts through the GCD technique. It is well-suited for scenarios with memory limitations, such as embedded systems or extensive datasets, thanks to its O(n) time complexity and O(1) space complexity. The fundamental concept of logically dividing items and rotating them around guarantees a robust and adaptable approach for manipulating arrays in the C++ programming language.