Array Rotation Left And Right in C

Array rotation is a fundamental operation in computer science, often used in algorithms and data manipulation.

In this article, you will learn how to perform left and right array rotations using various efficient C programming techniques.

Problem Statement

The problem of array rotation involves shifting elements of an array by a specified number of positions, either to the left or to the right. This operation is crucial in areas like image processing, cryptography, and data compression, where efficient element rearrangement is key. For instance, rotating an array [1, 2, 3, 4, 5] left by 2 positions results in [3, 4, 5, 1, 2].

Example

Let's consider an array: [1, 2, 3, 4, 5]

• Left Rotation by 2 positions: The elements 1 and 2 move to the end. The result is [3, 4, 5, 1, 2].
• Right Rotation by 2 positions: The elements 4 and 5 move to the beginning. The result is [4, 5, 1, 2, 3].

 

Background & Knowledge Prerequisites

To follow along with this article, you should have a basic understanding of:

• C programming language fundamentals (variables, data types, loops).
• Arrays in C (declaration, initialization, accessing elements).
• Functions in C (defining, calling, passing parameters).

 

Use Cases or Case Studies

Array rotation finds application in diverse scenarios:

1. Image Processing: Rotating images often involves rotating rows or columns of pixel data.
2. Cryptography: Certain encryption algorithms use bit or byte rotation to scramble data, enhancing security.
3. Data Compression: Cyclic shifts can be part of data transformation techniques to reveal patterns that allow for better compression.
4. Circular Buffers/Queues: Implementing data structures like circular queues or buffers where elements wrap around requires rotation logic for efficient management.
5. Algorithm Optimization: Some search or pattern matching algorithms can benefit from data rotation to simplify comparisons or reduce redundant computations.

 

Solution Approaches

We will explore several methods for both left and right array rotations.

Left Rotation Approaches

Approach 1: Rotate One by One

One-line summary: Repeatedly rotate the array by one position d times.

// Left Rotate Array One by One
#include <stdio.h>

// Function to left rotate array by one position
void leftRotateByOne(int arr[], int n) {
    int temp = arr[0]; // Store the first element
    for (int i = 0; i < n - 1; i++) {
        arr[i] = arr[i + 1]; // Shift elements to the left
    }
    arr[n - 1] = temp; // Place the stored element at the end
}

// Function to left rotate array by d positions
void leftRotate(int arr[], int n, int d) {
    for (int i = 0; i < d; i++) {
        leftRotateByOne(arr, n);
    }
}

// Function to print array elements
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\\n");
}

int main() {
    int arr[] = {1, 2, 3, 4, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    int d = 2; // Number of positions to rotate

    printf("Original array: ");
    printArray(arr, n);

    // Step 1: Call leftRotate function to rotate the array
    leftRotate(arr, n, d);

    printf("Left rotated array by %d positions: ", d);
    printArray(arr, n);

    return 0;
}

Run

Sample output:

Original array: 1 2 3 4 5 6 7 
Left rotated array by 2 positions: 3 4 5 6 7 1 2

 

Stepwise explanation:

1. The leftRotateByOne function takes the first element, saves it in a temporary variable (temp).
2. It then shifts all subsequent elements one position to their left (arr[i] = arr[i + 1]).
3. Finally, the saved temp element is placed at the last position of the array.
4. The leftRotate function repeatedly calls leftRotateByOne d times to achieve a total left rotation of d positions.

 

Approach 2: Using a Temporary Array

One-line summary: Copy the first d elements to a temporary array, then shift the remaining elements, and finally append the temporary elements.

// Left Rotate Array using Temp Array
#include <stdio.h>

// Function to left rotate array by d positions using a temporary array
void leftRotateTempArray(int arr[], int n, int d) {
    // Adjust d if it's greater than n to avoid unnecessary rotations
    d = d % n; 

    // Create a temporary array to store the first 'd' elements
    int temp[d];
    for (int i = 0; i < d; i++) {
        temp[i] = arr[i];
    }

    // Shift the remaining (n-d) elements to the front
    for (int i = d; i < n; i++) {
        arr[i - d] = arr[i];
    }

    // Copy the elements from the temporary array to the end of the original array
    for (int i = 0; i < d; i++) {
        arr[n - d + i] = temp[i];
    }
}

// Function to print array elements (re-used for brevity)
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\\n");
}

int main() {
    int arr[] = {1, 2, 3, 4, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    int d = 2; // Number of positions to rotate

    printf("Original array: ");
    printArray(arr, n);

    // Step 1: Call leftRotateTempArray function to rotate the array
    leftRotateTempArray(arr, n, d);

    printf("Left rotated array by %d positions: ", d);
    printArray(arr, n);

    return 0;
}

Run

Sample output:

Original array: 1 2 3 4 5 6 7 
Left rotated array by 2 positions: 3 4 5 6 7 1 2

 

Stepwise explanation:

1. First, the rotation count d is adjusted (d = d % n) to handle cases where d might be greater than the array size n.
2. A temporary array temp of size d is created. The first d elements of the original array are copied into temp.
3. The elements from index d to n-1 are shifted d positions to the left, filling the gap left by the first d elements.
4. Finally, the elements stored in the temp array are copied back into the original array, starting from index n-d, effectively appending them to the end.

 

Approach 3: Reversal Algorithm

One-line summary: Reverse the first d elements, reverse the remaining n-d elements, then reverse the entire array.

// Left Rotate Array using Reversal Algorithm
#include <stdio.h>

// Function to reverse a subarray arr[start...end]
void reverseArray(int arr[], int start, int end) {
    while (start < end) {
        int temp = arr[start];
        arr[start] = arr[end];
        arr[end] = temp;
        start++;
        end--;
    }
}

// Function to left rotate array by d positions using reversal
void leftRotateReversal(int arr[], int n, int d) {
    // Adjust d if it's greater than n
    d = d % n; 
    
    // Step 1: Reverse the first 'd' elements
    // Example: arr = [1, 2, 3, 4, 5, 6, 7], d = 2
    // Reverse [1, 2] -> [2, 1, 3, 4, 5, 6, 7]
    reverseArray(arr, 0, d - 1);
    
    // Step 2: Reverse the remaining 'n-d' elements
    // Example: [2, 1, 3, 4, 5, 6, 7]
    // Reverse [3, 4, 5, 6, 7] -> [7, 6, 5, 4, 3]
    // Array becomes: [2, 1, 7, 6, 5, 4, 3]
    reverseArray(arr, d, n - 1);
    
    // Step 3: Reverse the entire array
    // Example: [2, 1, 7, 6, 5, 4, 3]
    // Reverse [2, 1, 7, 6, 5, 4, 3] -> [3, 4, 5, 6, 7, 1, 2] (Left rotated)
    reverseArray(arr, 0, n - 1);
}

// Function to print array elements (re-used for brevity)
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\\n");
}

int main() {
    int arr[] = {1, 2, 3, 4, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    int d = 2; // Number of positions to rotate

    printf("Original array: ");
    printArray(arr, n);

    // Step 1: Call leftRotateReversal function to rotate the array
    leftRotateReversal(arr, n, d);

    printf("Left rotated array by %d positions: ", d);
    printArray(arr, n);

    return 0;
}

Run

Sample output:

Original array: 1 2 3 4 5 6 7 
Left rotated array by 2 positions: 3 4 5 6 7 1 2

 

Stepwise explanation:

1. The d value is adjusted using d = d % n.
2. The first d elements of the array (arr[0] to arr[d-1]) are reversed.
3. The remaining n-d elements of the array (arr[d] to arr[n-1]) are reversed.
4. Finally, the entire array (arr[0] to arr[n-1]) is reversed. This sequence of reversals correctly places the elements in their left-rotated positions.

 

Right Rotation Approaches

Approach 1: Rotate One by One (Right)

One-line summary: Repeatedly rotate the array by one position to the right d times.

// Right Rotate Array One by One
#include <stdio.h>

// Function to right rotate array by one position
void rightRotateByOne(int arr[], int n) {
    int temp = arr[n - 1]; // Store the last element
    for (int i = n - 1; i > 0; i--) {
        arr[i] = arr[i - 1]; // Shift elements to the right
    }
    arr[0] = temp; // Place the stored element at the beginning
}

// Function to right rotate array by d positions
void rightRotate(int arr[], int n, int d) {
    for (int i = 0; i < d; i++) {
        rightRotateByOne(arr, n);
    }
}

// Function to print array elements (re-used for brevity)
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\\n");
}

int main() {
    int arr[] = {1, 2, 3, 4, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    int d = 2; // Number of positions to rotate

    printf("Original array: ");
    printArray(arr, n);

    // Step 1: Call rightRotate function to rotate the array
    rightRotate(arr, n, d);

    printf("Right rotated array by %d positions: ", d);
    printArray(arr, n);

    return 0;
}

Run

Sample output:

Original array: 1 2 3 4 5 6 7 
Right rotated array by 2 positions: 6 7 1 2 3 4 5

 

Stepwise explanation:

1. The rightRotateByOne function saves the last element of the array in temp.
2. It then shifts all preceding elements one position to their right (arr[i] = arr[i - 1]).
3. Finally, the saved temp element is placed at the first position of the array.
4. The rightRotate function calls rightRotateByOne d times to complete the rotation.

 

Approach 2: Using a Temporary Array (Right)

One-line summary: Copy the last d elements to a temporary array, then shift the remaining elements, and finally prepend the temporary elements.

// Right Rotate Array using Temp Array
#include <stdio.h>

// Function to right rotate array by d positions using a temporary array
void rightRotateTempArray(int arr[], int n, int d) {
    // Adjust d if it's greater than n
    d = d % n; 

    // Create a temporary array to store the last 'd' elements
    int temp[d];
    for (int i = 0; i < d; i++) {
        temp[i] = arr[n - d + i];
    }

    // Shift the remaining (n-d) elements to the right
    // Iterate from right to left to avoid overwriting un-shifted values
    for (int i = n - 1; i >= d; i--) {
        arr[i] = arr[i - d];
    }

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

// Function to print array elements (re-used for brevity)
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\\n");
}

int main() {
    int arr[] = {1, 2, 3, 4, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    int d = 2; // Number of positions to rotate

    printf("Original array: ");
    printArray(arr, n);

    // Step 1: Call rightRotateTempArray function to rotate the array
    rightRotateTempArray(arr, n, d);

    printf("Right rotated array by %d positions: ", d);
    printArray(arr, n);

    return 0;
}

Run

Sample output:

Original array: 1 2 3 4 5 6 7 
Right rotated array by 2 positions: 6 7 1 2 3 4 5

 

Stepwise explanation:

1. The rotation count d is adjusted (d = d % n).
2. A temporary array temp of size d is created. The last d elements of the original array (arr[n-d] to arr[n-1]) are copied into temp.
3. The elements from index n-1 down to d are shifted d positions to the right, creating space at the beginning.
4. Finally, the elements from the temp array are copied back into the original array, starting from index 0, thus prepending them.

 

Approach 3: Reversal Algorithm (Right)

One-line summary: Reverse the entire array, then reverse the first d elements, and finally reverse the remaining n-d elements.

// Right Rotate Array using Reversal Algorithm
#include <stdio.h>

// Function to reverse a subarray arr[start...end] (re-used for brevity)
void reverseArray(int arr[], int start, int end) {
    while (start < end) {
        int temp = arr[start];
        arr[start] = arr[end];
        arr[end] = temp;
        start++;
        end--;
    }
}

// Function to right rotate array by d positions using reversal
void rightRotateReversal(int arr[], int n, int d) {
    // Adjust d if it's greater than n
    d = d % n; 
    
    // Step 1: Reverse the entire array
    // Example: arr = [1, 2, 3, 4, 5, 6, 7], d = 2
    // Reverse [1,2,3,4,5,6,7] -> [7,6,5,4,3,2,1]
    reverseArray(arr, 0, n - 1); 
    
    // Step 2: Reverse the first 'd' elements
    // Example: [7,6,5,4,3,2,1]
    // Reverse [7,6] -> [6,7,5,4,3,2,1]
    reverseArray(arr, 0, d - 1); 
    
    // Step 3: Reverse the remaining 'n-d' elements
    // Example: [6,7,5,4,3,2,1]
    // Reverse [5,4,3,2,1] -> [1,2,3,4,5]
    // Array becomes: [6,7,1,2,3,4,5] (Right rotated)
    reverseArray(arr, d, n - 1); 
}

// Function to print array elements (re-used for brevity)
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\\n");
}

int main() {
    int arr[] = {1, 2, 3, 4, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    int d = 2; // Number of positions to rotate

    printf("Original array: ");
    printArray(arr, n);

    // Step 1: Call rightRotateReversal function to rotate the array
    rightRotateReversal(arr, n, d);

    printf("Right rotated array by %d positions: ", d);
    printArray(arr, n);

    return 0;
}

Run

Sample output:

Original array: 1 2 3 4 5 6 7 
Right rotated array by 2 positions: 6 7 1 2 3 4 5

 

Stepwise explanation:

1. The d value is adjusted using d = d % n.
2. The entire array (arr[0] to arr[n-1]) is reversed.
3. Then, the first d elements of the now-reversed array (arr[0] to arr[d-1]) are reversed.
4. Finally, the remaining n-d elements (arr[d] to arr[n-1]) are reversed. This sequence of reversals correctly performs a right rotation.

 

Conclusion

Array rotation is a foundational operation with various applications in computer science and programming. We've explored several C programming approaches for both left and right rotations. While the 'one-by-one' method is intuitive for beginners, the 'temporary array' and 'reversal algorithm' generally offer more efficient solutions in terms of time complexity, especially for larger arrays and significant rotation counts. The reversal algorithm is particularly noteworthy for its O(N) time complexity and O(1) auxiliary space complexity.

Summary

Here are the key takeaways from this article:

• Array Rotation: Shifting elements of an array by a specified number of positions, either to the left or to the right.
• Left Rotation: Elements move towards the beginning of the array, and elements shifted out from the beginning wrap around to the end.
• Right Rotation: Elements move towards the end of the array, and elements shifted out from the end wrap around to the beginning.
• Methods Explored for Both Directions:
• One by One: Simple to implement but less efficient (O(N\*D) time complexity).
• Temporary Array: More efficient than one-by-one (O(N) time, O(D) space complexity).
• Reversal Algorithm: Often the most efficient in-place method (O(N) time, O(1) auxiliary space complexity).
• Prerequisites: Basic C knowledge, including arrays and functions, is essential.
• Use Cases: Image processing, cryptography, circular buffers, and various algorithmic optimizations.

 

Test Your Knowledge

1. What is the main advantage of the reversal algorithm over the temporary array approach for array rotation?
2. If an array [Z, Y, X, W] is right-rotated by 1 position, what is the resulting array?
3. Describe a real-world scenario where a left array rotation might be more appropriate than a right rotation.

Challenge yourself: Explore and implement the Juggling Algorithm (GCD-based) for array rotation, which offers another efficient in-place solution!