Tuesday 10 September 2013

Rotate the array

Example
Input : {1, 2, 3, 4, 5},  rotate Index = 2
Output: {3, 4, 5, 1, 2}

Algorithm :
   1. Divide the given array into 2 groups at given rotate-index.(Group-A and Group-B)
   2. Group-A' = Reverse first group Group-A.
   3. Group-B' = Reverse second group Group-B.
   4. Reverse {Group-A', Group-B'}

How?:
let us consider the array = {1, 2, 3, 4, 5} and rotated index = 2.
then Group-A = {1, 2}
Group-B ={3, 4, 5}
{1, 2, 3, 4, 5} = {Group-A, Group-B}

Now reverse first group Group-A :
  Group-A' = reverse(Group-A)
  Group-A' = {2, 1}

Now reverse second group Group-B :
  Group-B' = reverse(Group-B)
  Group-B' = {5, 4, 3}

Now reverse {Group-A' , Group-B'} = {3, 4, 5, 1, 2}

Implementation

class RotateArray{
        public static void rotate(int []a, int k){
               reverse(a, 0, k-1);   //reverse the first group
               reverse(a, k, a.length - 1);   //reverse the second group
               reverse(a, 0, a.length - 1);  //reverse the array
        }
    
        public static void reverse(int []a, int start, int end){
               if( a.length < end-start)
                     return;
        
               for(; start < end; start++, end--){
                     int t = a[end];
                     a[end] = a[start];
                     a[start] = t;
               }
        }
    
        public static void main(String []args){
               int []a = {1,2,3,4,5};
               rotate(a,2);
              System.out.println(java.util.Arrays.toString(a));
        }  
}

Output : 3, 4, 5, 1, 2

No comments:

Post a Comment