Rotating an array:
In this post we will discuss two solutions for rotating an array by a given number of times. One is a simple solution and another uses the reversal operation (discusses in the previous post).
Method#1: Simple and intuitive
In this method, we will copy the last element into a variable, and shift all the elements right by one step, and copy the stored element into the empty spot created at the beginning of the array. We repeat this for the given number of times.
Method#2: Using reversal algorithm
I have taken this algorithm from here. It is a three step procedure. Let array[0:n-1] be the array, and ‘s’ be the number of times to rotate the array.
step 1: Reverse the sub-array array[0:s-1]
step 2: Reverse the sub-array array[s:n-1]
step 3: Reverse the whole array i.e array[0:n-1]
For example let the array be [7 1 2 3 8], and it is to be rotated 3 times
here is how it works
step 1: [2 1 7 3 8]
step 2: [2 1 7 8 3]
step 3: [3 8 7 1 2]
C++ implementation of the above two methods is given below.
#include <iostream>
#include <string>
using namespace std;
//right rotates array of size n by s positions
//assumes that n > 1 (atleast 2 elements) and s < n
void rotateSimple( int* array, int n, int s)
{
int i;
int j;
for( i = 0 ; i < s ; i++ )
{
//store the last element
int last = array[n-1];
//shift all elements right by one
for( j = n-2 ; j >= 0 ; j-- )
{
array[j+1] = array[j];
}
//copy stored element to the beginning
array[0] = last;
}
}
//helper method for reversal
void swap( int &a, int &b)
{
int temp = a;
a = b;
b = temp;
}
//function to reverse the sub-array array[low to high
void reverseArray(int *array, int low, int high)
{
while( low < high ) //until both ends meet
{
swap( array[low], array[high] ); //swap the elements
low++; //increment left
high--;//decrement right
}
}
//rotate the array using reversal operation
void rotateByReverse(int* array,int n, int s)
{
reverseArray(array,0,s-1);
reverseArray(array,s,n-1);
reverseArray(array,0,n-1);
}
//utlity to print the array
void printArray(int * array,int n)
{
for( int i = 0; i < n; i++ )
{
cout<<array[i]<<" ";
}
cout<<endl;
}
int main()
{
int n; //array size
int s; //rotation count
//read array size, and rotation count
cin>>n>>s;
//dynamically allocate array based on input size
int *array = new int[n];
int i;
for( i = 0 ; i < n; i++ )
{
cin>>array[i];
}
//call rotate function
rotateByReverse( array, n, s);
printArray( array, n);
//release the memory
delete[] array;
return 0;
}