Thursday, January 13, 2011

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. First, we reverse the first half of the array--starting from index 0 to (rotate index - 1). Then we reverse the second half of the array--starting from rotate index to the last index of the array. Lastly, we reverse the whole array.

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.

Note:The functions didn't include error checking procedures. You can improve them by writing your own error-checking code :)

No comments:

Post a Comment