Monday, May 13, 2013

Rotating an array

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;
}