Friday, January 6, 2012

How to rotate an array?

One of the classic problems with array is to perform in-place rotation on the array. For example, if we have an array of integers such as int[]array = new int[]{1, 2, 3, 4, 5, 6} and we want to rotate it around index 2, then the rotated array is {3, 4, 5, 6, 1, 2}. So, how can we rotate an array around a given index? Well here is the algorithm with explanation follows after:
public void reverseArray(int[] array, int start, int end)
{
 int i;
 int temp;

 while (start < end)
 {
  temp = array[start];
  array[start] = array[end];
  array[end] = temp;
  start++;
  end--;
 }
}

private static void rotateArrayByIndex(int array[], int rotatePos, int arraySize)
{
 reverseArray(array, 0, rotatePos - 1);
 reverseArray(array, rotatePos, arraySize - 1);
 reverseArray(array, 0, arraySize - 1);
}
The strategy consists of three steps(consider the array - 1, 2, 3, 4, 5, 6).
  • First, we reverse the first half of the array--starting from index 0 to (rotate index - 1).
    rotateIndex = 2, hence array becomes = 2,1....3,4,5,6
  • Then we reverse the second half of the array--starting from rotate index to the last index of the array. 2,1....6 5 4 3
  • Lastly, we reverse the whole array.
    3, 4, 5, 6, ...1,2
The first function reverses a specific portion of an array. It's simple. We just swap the last element with the first element, the second to last element with the second element and so on until the start and end indices meet.
Once we have the reverse function, the rotate function is trivial. rotateArrayByIndex does the three steps that we outlined above in order to rotate an input array by a specified index.

More and source - http://stackoverflow.com/questions/4457277/algorithm-to-rotate-an-array-in-linear-time

0 comments:

Post a Comment