Rotating an array around a pivot

Given an Array of (say) integers like below:

1 2 3 4 5 6 7 8

and an index, say, 2. Write a function which will rotate the array around index 2. i.e the output should be:

3 4 5 6 7 8 1 2

Solution:

There are many ways to perform the pivoted rotation of an array. Method-1 and 2 are not-so-efficient, look for approach 3 and 4 for a good algorithm

1. Rotate one element at a time

// d is the point (index) where we have to rotate
for(i=1; i<=d; i++)
{
    int temp = arr[0];
    for(int cnt=1; cnt<n; cnt++)
        arr[cnt-1] = arr[cnt];
    arr[n-1] = temp;
}

Time complexity: O(n * d)
Extra Space: O(1)

2. Use a temporary array

1. Use a temporary array of size d and
2. store the first d elements of original array in temporary array,
3. shift all the elements of original array by d positions towards left
4. copy the elements of temporary array at the rear of original array

int * temparr = new int[d];
int i=0;
for(i=0; i<d; i++)
    temparr[i] = arr[i];
for(i=0; i<n-d; i++)
    arr[i] = arr[i+d];
for(; i<n; i++)
    arr[i] = temparr[i-n+d];
delete temparr;

Time Complexity: O(n)
Extra Space Used: O(d)

3. Use Vector Rotation

To learn about this method refer below link.

http://www.cs.bell-labs.com/cm/cs/pearls/s02b.pdf

4. Reversal Algorithm

I find this a very interesting algorithm to rotate array. The algo is as below:

Let us write a function reverse which reverse an array between two indexes, The signature of the function will be as below:

void reverse(int *arr, int start, int end);

and it will reverse the subarray from start to end (both indexes inclusive). Its easy to implement (you have to just swap all the elements in first half of sub-array with corresponding second half element). reverse(arr, 0, n); will reverse the entire array.

Now the algorithm to rotate array will be like below:

1. reverse(arr, 0, d-1);
2. reverse(arr, d, n-1);
3. reverse(arr, 0, n-1);

i.e reverse the first half, then reverse the second half and finally reverse the entire array.

If input array is 1 2 3 4 5 6 7 8, then

reverse(arr, 0, 1);  // 2 1 3 4 5 6 7 8
reverse(arr, 2, 7);  // 2 1 8 7 6 5 4 3
reverse(arr, 0, 7);  // 3 4 5 6 7 8 1 2

I don’t think I need to write code for this, but if you still find any difficulty, do let me know.