Monday, January 21, 2013

C Program to Rotate array by k times

Lets assume you have array of n=7 elements . And if u rotate it by k=3 times the input and output will be
I/P :  1 2 3 4 5 6 7
O/P: 5 6 7 1 2 3 4

This can be done in 3 steps.

Steps are:
i) reverse the whole array  ( 7 6 5 4 3 2 1 ).
ii)reverse first k elements ( 5 6 7 4 3 2 1 ).
ii)reverse the remaining n-k elements (5 6 7 1 2 3 4).

Note : And here's the thing. You have the reverse module in common .So write it as a separate function  ( modularity ) and it can be reused ( reusability ) . And if k is greater than we don't need to rotate it k times. For an example if u rotate the array by 7 times the output will be 1 2 3 4 5 6 7 (same as input) . so if k is 9 it is equal to rotating array by 2 times.

Code : (in C) 

void rotate_array(int* array,int n,int k)
{
if(n < 1 || k < 1)
return ;
if(k > n)
k=k%n;
reverse_array(array,0,n-1);
reverse_array(array,0,k-1);
reverse_array(array,k,n-1);
}

void reverse_array(int* array,int first,int last)
{
if(first>=last)
return;
int temp;
while(first < last)
{
temp=array[first];
array[first]=array[last];
array[last]=temp;
first++;
last--;
}
}

Please let me know if there is any bug in the above code and your suggestions are always welcome .

No comments: