Write A C++ Program To Make A Circular Rotation Of An Array By

Arrays are fundamental data structures that often require manipulation. One common operation is circular rotation, where elements shift positions, and those moving off one end reappear at the other. In this article, you will learn how to implement circular array rotation by k positions in C++ using different loop-based techniques.

Problem Statement

Circular array rotation involves shifting all elements of an array by a specified number of positions (k) to either the left or the right. Elements that move beyond the array boundaries re-enter from the opposite end, maintaining a "circular" structure. This operation is crucial in various computational tasks where data ordering needs to be dynamically adjusted while preserving all original elements.

Example

Consider an array: [10, 20, 30, 40, 50] If we perform a circular right rotation by k = 2 positions, the output will be: [40, 50, 10, 20, 30]

Background & Knowledge Prerequisites

To understand and implement the solutions effectively, readers should have a basic understanding of:

• C++ Syntax: Variables, data types, operators.
• Arrays: Declaration, initialization, and access.
• Loops: for and while loops for iteration.
• Functions: Defining and calling functions.

 

No special libraries or complex data structures are required beyond standard C++ features.

Use Cases or Case Studies

Circular array rotation finds applications in diverse fields:

• Image Processing: Shifting pixel data for visual effects or analysis.
• Cryptography: Implementing certain encryption or permutation algorithms that rely on cyclic shifts of data blocks.
• Game Development: Rotating game elements or textures on a screen.
• Data Buffering: Managing circular buffers where older data is overwritten by newer data after a full cycle.
• Scheduling Algorithms: Adjusting task queues or resource allocation in a cyclic manner.

 

Solution Approaches

We will explore two common loop-based approaches to perform circular array rotation.

Approach 1: Using a Temporary Array

This approach involves creating a temporary array to store the elements that will be moved to the beginning of the array after rotation.

• One-line summary: Store the last k elements in a temporary array, shift the remaining n-k elements to the right, then place the temporary elements at the beginning.

 

// Circular Array Rotation using Temporary Array
#include <iostream>
#include <vector> // Using std::vector for dynamic array
#include <numeric> // For std::iota if needed for initialization (not used in example)

void rotateArrayTemp(std::vector<int>& arr, int k) {
    int n = arr.size();
    if (n == 0) return; // Handle empty array
    k = k % n; // Normalize k to be within array bounds (0 to n-1)

    // Create a temporary vector to store the last k elements
    std::vector<int> temp(k);
    for (int i = 0; i < k; ++i) {
        temp[i] = arr[n - k + i];
    }

    // Shift the first n-k elements to the right by k positions
    for (int i = n - 1; i >= k; --i) {
        arr[i] = arr[i - k];
    }

    // Copy the elements from the temporary vector to the beginning of the original array
    for (int i = 0; i < k; ++i) {
        arr[i] = temp[i];
    }
}

int main() {
    // Step 1: Define the array and rotation amount
    std::vector<int> my_array = {10, 20, 30, 40, 50};
    int k_positions = 2;

    std::cout << "Original Array: ";
    for (int x : my_array) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    // Step 2: Call the rotation function
    rotateArrayTemp(my_array, k_positions);

    // Step 3: Print the rotated array
    std::cout << "Rotated Array (k=" << k_positions << "): ";
    for (int x : my_array) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    // Example with k > n
    std::vector<int> another_array = {1, 2, 3};
    int k_large = 4;
    std::cout << "\\nOriginal Array: ";
    for (int x : another_array) {
        std::cout << x << " ";
    }
    std::cout << std::endl;
    rotateArrayTemp(another_array, k_large);
    std::cout << "Rotated Array (k=" << k_large << ", normalized to k=1): ";
    for (int x : another_array) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    return 0;
}

Run

• Sample Output:

Original Array: 10 20 30 40 50 
Rotated Array (k=2): 40 50 10 20 30 

Original Array: 1 2 3 
Rotated Array (k=4, normalized to k=1): 3 1 2

 

• Stepwise explanation for clarity:

1. Normalize k: Calculate k = k % n to handle cases where k is greater than or equal to the array size n. This ensures k represents the effective number of rotations.
2. Store last k elements: A temporary std::vector of size k is created. The elements from arr[n-k] to arr[n-1] are copied into this temporary array.
3. Shift remaining elements: The elements from arr[0] to arr[n-k-1] are shifted k positions to the right. This is done by iterating from n-1 down to k, moving arr[i-k] to arr[i].
4. Place stored elements: Finally, the elements from the temporary array are copied back to the beginning of the original array, from arr[0] to arr[k-1].

Approach 2: Repeatedly Rotating by One Position

This method performs the rotation by repeatedly shifting the array elements one position at a time, k times.

• One-line summary: Rotate the array by one position k times, where each single rotation moves the last element to the front and shifts all other elements one position to the right.

 

// Circular Array Rotation by One Position Repeatedly
#include <iostream>
#include <vector> // Using std::vector for dynamic array

void rotateArrayOneByOne(std::vector<int>& arr, int k) {
    int n = arr.size();
    if (n == 0) return; // Handle empty array
    k = k % n; // Normalize k

    // Perform k rotations
    for (int rotation_count = 0; rotation_count < k; ++rotation_count) {
        int last_element = arr[n - 1]; // Store the last element

        // Shift all elements from n-2 down to 0 one position to the right
        for (int i = n - 1; i > 0; --i) {
            arr[i] = arr[i - 1];
        }

        arr[0] = last_element; // Place the stored last element at the beginning
    }
}

int main() {
    // Step 1: Define the array and rotation amount
    std::vector<int> my_array = {1, 2, 3, 4, 5};
    int k_positions = 2;

    std::cout << "Original Array: ";
    for (int x : my_array) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    // Step 2: Call the rotation function
    rotateArrayOneByOne(my_array, k_positions);

    // Step 3: Print the rotated array
    std::cout << "Rotated Array (k=" << k_positions << "): ";
    for (int x : my_array) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    // Another example
    std::vector<int> small_array = {7, 8, 9};
    int k_small = 1;
    std::cout << "\\nOriginal Array: ";
    for (int x : small_array) {
        std::cout << x << " ";
    }
    std::cout << std::endl;
    rotateArrayOneByOne(small_array, k_small);
    std::cout << "Rotated Array (k=" << k_small << "): ";
    for (int x : small_array) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    return 0;
}

Run

• Sample Output:

Original Array: 1 2 3 4 5 
Rotated Array (k=2): 4 5 1 2 3 

Original Array: 7 8 9 
Rotated Array (k=1): 9 7 8

 

• Stepwise explanation for clarity:

1. Normalize k: Similar to the first approach, k is normalized to k % n.
2. Outer Loop (k times): An outer loop runs k times, with each iteration performing a single right rotation.
3. Store Last Element: Inside the outer loop, the last element of the array (arr[n-1]) is stored in a temporary variable (last_element).
4. Shift Elements: An inner loop shifts all elements from arr[n-2] down to arr[0] one position to the right. This means arr[i] gets arr[i-1].
5. Place Stored Element: After the shift, the last_element (which was originally at arr[n-1]) is placed at the beginning of the array (arr[0]).

Conclusion

Circular array rotation is a fundamental operation in computer science with several practical applications. We've explored two distinct loop-based methods for performing this task in C++. The temporary array method offers a more direct approach by shifting blocks of data, while the repeated single rotation method provides a simpler, albeit potentially less efficient for very large k, conceptual understanding of the rotation process. Both methods successfully achieve the desired circular shift using basic loop constructs.

Summary

• Circular Rotation: Shifting array elements where ends wrap around.
• Normalization of k: Always use k = k % n to handle k values greater than array size.
• Temporary Array Approach:
• Efficient for larger arrays and k.
• Requires O(k) auxiliary space for the temporary array.
• Time complexity: O(n) as elements are iterated and moved a constant number of times.
• Repeated Single Rotation Approach:
• Simple to understand and implement.
• Does not require extra space (in-place rotation).
• Time complexity: O(n*k) because an O(n) operation is repeated k times, making it less efficient for large k.
• Choose the appropriate approach based on performance requirements and memory constraints.