ADVERTISEMENT
ADVERTISEMENT

Reversal Algorithm of Array Rotation

Learn about the Reversal Algorithm of Array Rotation and its implementation using C++ program.
Submitted by Vikneshwar GK, on February 12, 2022

Consider an integer array of size n and an integer d. The task at hand is to rotate the elements anti-clockwise by d elements, i.e., place the first d elements at the end of the array by pushing the remaining elements to the front.

Example:

Input:
array[]= {1, 2, 3, 4, 5}
d = 3

Output:
array[] = {4, 5, 1, 2, 3}

Input:
array[]= {10, 20, 30, 40, 50}
d = 1

Output:
array[]= {20, 30, 40, 50, 10}

Solution: Reversal algorithm

This algorithm divides the array into two groups. The first group consists of array elements from 0 to d-1 and the second group from d to n-1, where n is the length of the array. It involves the following steps:

  • Reverse the array[0..d-1]
  • Reverse the array[d..n-1]
  • Reverse the array completely
  • Print the array

Consider the following example:

  • If array[] = {1, 2, 3, 4, 5, 6} and d = 3,
  • After 1st reversal, array will be array[] = {3, 2, 1, 4, 5, 6}
  • After 2nd reversal, array will be array[] = {3, 2, 1, 6, 5, 4}
  • After 3rd reversal, array will be array[] = {4, 5, 6, 1, 2, 3}

C++ Implementation:

#include <bits/stdc++.h>
using namespace std;

// Function to reverse the array
void arrayReverse(int array[], int begin, int end)
{
    while (begin < end) {
        int temp = array[begin];
        array[begin] = array[end];
        array[end] = temp;
        begin++;
        end--;
    }
}

// Function to rotate the array by reversing
void rotate(int array[], int d, int length)
{
    if (d == 0)
        return;

    // case to handle when d greater than length
    d = d % length;

    // array reverse
    arrayReverse(array, 0, d - 1);
    arrayReverse(array, d, length - 1);
    arrayReverse(array, 0, length - 1);
}

// Function to print the array
void printArray(int array[], int length)
{
    for (int i = 0; i < length; i++)
        cout << array[i] << " ";
    cout << endl;
}

// Main function
int main()
{
    int array[100], N, d;
    
    cout << "Enter Number of elements: ";
    cin >> N;

    for (int i = 0; i < N; i++) {
        cout << "Enter element " << i + 1 << ":";
        cin >> array[i];
    }
    cout << "Enter the value of d: ";
    cin >> d;

    rotate(array, d, N);
    cout << "Rotated Array" << endl;
    printArray(array, N);

    return 0;
}

Output:

Enter Number of elements: 6
Enter element 1:2
Enter element 2:4
Enter element 3:6
Enter element 4:8
Enter element 5:10
Enter element 6:12
Enter the value of d: 4
Rotated Array
10 12 2 4 6 8

Time Complexity: O(n), where n is the length of the array.

ADVERTISEMENT
ADVERTISEMENT


Comments and Discussions!



ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT

Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing
» Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates

© https://www.includehelp.com some rights reserved.