Algorithm to rotate an array in linear time
You can do this in linear time by using a reverse() helper.
// rotate array of size=size, by n positions
void rotate(int array[], int size, int n)
{
// reverse array[0...size-1]
reverse(array, 0, size-1);
// reverse A[0...n-1]
reverse(array, 0, n-1);
// reverse A[n...size-1]
reverse(array, n, size-1);
}
// reverse elements in the array[pos_from ... pos_to]
void reverse(int array[], int pos_from, int pos_to)
{
...
}
Implementing reverse(int array[], int pos_from, int pos_to)
using swaps is left as an exercise for the reader. Hint: This can be done in linear time.
Let us say we have a function called arr_reverse(arr,i,j)
which reverses the elements of the array arr
between index i
and j
using the swap
function.
Example:
arr = {1,2,3,4,5}
i = 0
j = 2
then the function will return:
{3,2,1,4,5}
^^^^^
Implementing this function is straight forward and is O(N)
.
Now let's use this function in rotating the array.
arr = {1,2,3,4,5} // input array
k = 2 // amount of right rotation
result = {4,5,1,2,3} // expected result
l = 5 // length of array.
Step 1: Call arr_reverse(arr,l-k,l-1) which is arr_reverse(arr,3,4)
we get {1,2,3,5,4}
^^^
Step 2: Call arr_reverse(arr,0,l-k-1) which is arr_reverse(arr,0,2)
we get {3,2,1,5,4}
^^^^^
Step 3: Call arr_reverse(arr,0,l-1) which is arr_reverse(arr,0,4)
we get {4,5,1,2,3}
^^^^^^^^^
The entire process makes use of arr_reverse
3 times, making it O(N)
Here's a better solution, of a different nature than the others. It involves fewer array swaps than the others. Python:
import fractions
# rotates an array in-place i positions to the left, in linear time
def rotate(arr,i):
n = len(arr)
reps = fractions.gcd(n,i)
swaps = n / reps
for start in xrange(reps):
ix = start
tmp = arr[ix]
for s in xrange(swaps-1):
previx = ix
ix = (ix + i) % n
arr[previx] = arr[ix]
arr[ix] = tmp
return arr
Using linear time O(2N+m), and constant space O(4). m = GCD(n, p)
It's up to 50% faster than the swapping approach, because swapping requires writing O(N) times to a temporary.
http://www.eis.mdx.ac.uk/staffpages/r_bornat/oldteaching/I2A/slides%209%20circshift.pdf
for (m=0, count=0; count!=n; m++) {
type t=A[m];
for (i=m, j=m+p; j!=m; i=j, j = j+p<n ? j+p : j+p-n, count++)
A[i]=A[j];
A[i]=t; count++;
}