## Rotate An Array

### October 12, 2010

The easy solution is to write functions to rotate the array a single element in each direction, then call the functions for the requested count. But that means lots of intermediate assignments, so it’s slow. Instead, three well-chosen reversals can perform any rotation with a minimum of movement.

We first define a function `swap!` that exchanges two elements of a vector:

```(define (swap! v i j)   (let ((t (vector-ref v i)))     (vector-set! v i       (vector-ref v j))     (vector-set! v j t)))```

`Swap!` is called by `reverse!`, which exchanges the two elements at its endpoints, then calls itself recursively on the intermediate sub-vector, stopping when the two indices cross:

```(define (reverse! v lo hi)   (when (< lo hi)     (swap! v lo hi)     (reverse! v (+ lo 1) (- hi 1))))```

Then `rotate!` reduces n modulo the length of the vector (you should confirm that this works properly whether n is positive, negative or zero) and makes three reversals. First the left half of the vector, from 0 to n-1, is reversed. Then the right half of the vector, from n to len-1, is reversed. Finally the entire vector is reversed. This leaves the vector rotated as requested:

```(define (rotate! n v)   (let* ((len (vector-length v))          (n (modulo n len)))     (reverse! v 0 (- n 1))     (reverse! v n (- len 1))     (reverse! v 0 (- len 1))))```

If this seems like magic, watch what happens on our sample vector when we rotate two positions to the left. The original vector is [1 2 3 4 5 6]. Reversing the two left positions gives us [2 1 3 4 5 6]. Reversing the remaining four positions gives us [2 1 6 5 4 3]. One final reversal yields the desired result [3 4 5 6 1 2].

Jon Bentley described this algorithm for rotating an array in his Programming Pearls books, and includes pretty hand-waving pictures. Brian Kernighan and P J Plauger described it earlier, in their Software Tools books. The algorithm dates to the folklore of computing.

You can run the program at http://programmingpraxis.codepad.org/QKrX5JfK.

Pages: 1 2

### 23 Responses to “Rotate An Array”

1. […] today’s Programming Praxis exercise, our goal is to write a function to rotate an array a selected number […]

2. Remco Niemeijer said

```rotate :: Int -> [a] -> [a]
rotate _ [] = []
rotate n xs = b ++ a where (a,b) = splitAt (mod n \$ length xs) xs
```

On a side note, the given Scheme solution fails on arrays of length 0.

3. Graham said

Python solution, similar logic to Remco’s Haskell:

```def rotate(array, nelts):
n = nelts % len(array)
return array[n:] + array[:n]
```
4. Jake said

Here’s my solution in F#. Had to do a bit of extra work because of the way the modulus operator is defined.

5. http://pastebin.com/5wKvVgWG

Rotate in place with exactly n swaps and attempts to have fairly good locality.

6. Abie said

À la Racket. This is the first time I’ve used multiple return values.

#lang racket
(require (only-in rnrs/base-6 mod))

(define (rotate a-vector rot)
(if (<= (vector-length a-vector) 1)
a-vector
(call-with-values
(λ ()
(vector-split-at a-vector (mod rot (vector-length a-vector))))
(λ (1st 2nd)
(vector-append 2nd 1st)))))

7. Axio said

;; Common lisp
;; Does return the original array, not a chunk of a circular list like
;; “rot l n = take (length l) \$ drop (if (n>0) then n else (abs ((length l) – n))) \$ cycle l”
(defun rotate (arr n)
(let* ((arlen (length arr))
(new-arr (make-array arlen)))
(loop for i below arlen
do
(setf (aref new-arr i) (aref arr (mod (+ i n) arlen))))
(loop for i below arlen
do
(setf (aref arr i) (aref new-arr i)))))

8. Jim Rees said

;; Simple, bulletproof.

(define (reverse-range! v start end)
(do ((i start (+ i 1))
(j (- end 1) (- j 1)))
((>= i j) v)
(let ((tmp (vector-ref v i)))
(vector-set! v i (vector-ref v j))
(vector-set! v j tmp))))

(define (vector-rotate! v n)
(let ((N (vector-length v)))
(unless (zero? N)
(let ((n (modulo n N)))
(reverse-range! v 0 n)
(reverse-range! v n N)
(reverse-range! v 0 N)))
v))

9. Leandro Pacheco said

Using python list comprehensions:

def rotate_array(arr, rotation):
return [arr[(rotation + i) % len(arr)] for i in range(len(arr))]

10. Lars Björnfot said

Here is a Java version. No recursion, just one plain loop.
Not the shortest solution but it handles all edge cases
(including larger left rotate than array size).

```public int[] rotate(int[] array, int count) {
int length = array.length;
if (length == 0 || count % length == 0)
return array;
count = ((count % length) + length) % length; // limit and make positive
int[] dest = new int[length];
for (int i=0; i<length; i++) {
int index = (i + count) % length;
dest[index] = array[i];
}
return dest;
}
```
11. nozx said

;; common lisp
(defun rotate (lst arg)
(cond
((null lst) lst)
((= (mod arg (length lst)) 0) lst)
(t (rotate (nconc (cdr lst) (list (car lst))) (- arg 1)))))

12. Xenmen said

The key here is to NOT use a premade rotate function. Here’s my solution in Python:

def rotator(arrayOld, rotateValue):
arrayLength = arrayOld.__len__()
while rotateValue > arrayLength: rotateValue -= arrayLength
while rotateValue 0:
for i in range(arrayLength):
if i < rotateValue: arrayNew_buffer.append(arrayOld[i])
else: arrayNew.append(arrayOld[i])
else:
for i in range(arrayLength):
if i < (arrayLength + rotateValue): arrayNew_buffer.append(arrayOld[i])
else: arrayNew.append(arrayOld[i])
for i in arrayNew_buffer: arrayNew.append(i)
return arrayNew

/*This is My C Implementation */

#include
#include

int *rotate(int *a,int size,int count)
{

int *c,j,temp,k=0,sign;

c=(int *)calloc(size,sizeof(int));

sign =count>>31;

temp=(sign==-0x01)? (size-(-count)) : count;

for(j=(temp);j<size;j++)
{
c[k]=a[j];
k++;
}

for(j=0;j<(temp);j++)
{
c[k]=a[j];
k++;}

a=c;

return a;
}

int main()
{
int *b,cnt,size,i;

printf("Enter size of Array?");
scanf("%d",&size);

b=(int *)calloc(size,sizeof(int));
for(i=0;i<size;i++)
scanf("%d",&b[i]);

while(1)
{
printf("No of elements to rotate?\n\t\tPositive Value to Rotate Left \n\t\tNegative to Right \n\t\tEnter '0' to Quit\n");
scanf("%d",&cnt);
if(cnt==0)
{
exit(0);
}
else{
cnt=cnt%size;
b=rotate(b,size,cnt);
printf("rotated array \n");
for(i=0;i<size;i++)
printf("\t%d",b[i]);
}

}
return 0;
}

#include
#include

int *rotate(int *a,int size,int count)
{

int *c,j,temp,k=0,sign;

c=(int *)calloc(size,sizeof(int));

sign =count>>31;

temp=(sign==-0x01)? (size-(-count)) : count;

for(j=(temp);j<size;j++)
{
c[k]=a[j];
k++;
}

for(j=0;j<(temp);j++)
{
c[k]=a[j];
k++;}

a=c;

return a;
}

int main()
{
int *b,cnt,size,i;

printf("Enter size of Array?");
scanf("%d",&size);

b=(int *)calloc(size,sizeof(int));
for(i=0;i<size;i++)
scanf("%d",&b[i]);

while(1)
{
printf("No of elements to rotate?\n\t\tPositive Value to Rotate Left \n\t\tNegative to Right \n\t\tEnter '0' to Quit\n");
scanf("%d",&cnt);
if(cnt==0)
{
exit(0);
}
else{
cnt=cnt%size;
b=rotate(b,size,cnt);
printf("rotated array \n");
for(i=0;i<size;i++)
printf("\t%d",b[i]);
}

}
return 0;
}

15. lalit mohan said

My Solution in python:

16. Chil Tlalli said

You guys rock – I’m learning so much by seeing your solutions!

Here’s my emacs lisp implementation (using a list to hold the array):
``` (defun rot8r(a n) (if (= 0 (length a)) a (progn (append (nthcdr (mod n (length a)) a) (butlast a (- (length a) (abs (mod n (length a))))) )))) ```

17. […] Programming Praxis, Rotate An Array. I think of it more like an offset. Shift an array’s contents by ±x spaces. public static […]

18. ckknight said

Here’s mine in C#.

```static void RotateArrayInplace<T>(T[] array, int count)
{
count %= array.Length;
if (count == 0)
return;
else if (count < 0)
count += array.Length;

T[] tmp = new T[count];
Array.Copy(array, tmp, count);
Array.Copy(array, count, array, 0, array.Length - count);
Array.Copy(tmp, 0, array, array.Length - count, count);
}

static T[] RotateArray<T>(T[] array, int count)
{
count %= array.Length;
if (count == 0)
return (T[])array.Clone();
else if (count < 0)
count += array.Length;

T[] result = new T[array.Length];
Array.Copy(array, 0, result, array.Length - count, count);
Array.Copy(array, count, result, 0, array.Length - count);
return result;
}
```
19. Jebb said

Did it in C, rotating the array in place instead of returning a new one. The actual rotation in my solution involves (n + gcd(n, offset)) assignments, using no additional memory appart from a single temp variable. If n and offset are coprime, we can rotate the array in a single pass; if not, we need to break it down in gcd(n, offset) sub-problems.

```void rotate(int *array, int len, int offset)
{
int i, j, gcd, tmp;
while (offset < 0)
offset += len;
gcd = _gcd(offset,len);
for (j = 0; j < gcd; j++) {
tmp = array[offset % len + j];
for (i = len / gcd; i > 1; i--)
array[(i + 1) * offset % len + j] = array[i * offset % len + j];
array[2 * offset % len + j] = tmp;
}
}```

(the _gcd function is the one we’ve written for the 15 January 2010 exercise)

I find the code hard to understand, don’t know how to make it any easier to read. To help clarify a bit, here’s what’s happening when rotating an array of length 9 by an offset of 5:
5 -> tmp
0 -> 5
4 -> 0
8 -> 4
3 -> 8
7 -> 3
2 -> 7
6 -> 2
1 -> 6
tmp -> 1

and the same array by an offset of 6:
6 -> tmp
0 -> 6
3 -> 0
tmp -> 3
7 -> tmp
1 -> 7
4 -> 1
tmp -> 4
8 -> tmp
2 -> 8
5 -> 2
tmp -> 5

20. hash1baby said

This can be done with constant space cost, since translation by offset = reflection at origin followed by reflection at (origin + offset). Reflection can be implemented by swapping elements pairwise in place.

21. Atif Farooq said

Hello I am new
//_________________________________________________________//

#include

using namespace std;

//_________________________________________________________//

//Function to Determine Absolute and to account for Extremities

int AbsolShiftfunc (int User , int ArrSize)

{

int Absolshift;

int ShiftType;

if (User>=0)

{

Absolshift = User;

ShiftType = 1;

if (UserArrSize)

{

while(Absolshift>ArrSize)

{

Absolshift = Absolshift – ArrSize;

}

}

}

else if (User<=0)

{

Absolshift = -User;

ShiftType = 0;

if (-User ArrSize)

{
while(Absolshift>ArrSize)

{

Absolshift = Absolshift – ArrSize;

}

}

}

if (ShiftType == 1)

{

return Absolshift;

}

else if (ShiftType == 0)

{

return -Absolshift;

}

}

//_________________________________________________________//

int IndivShiftfunc (int Initial , int Absolshift, int ArrSize)

{

int Destindex = Initial+(Absolshift);

if (Destindex >= ArrSize )

{
while (Destindex >= ArrSize)

{

Destindex = Destindex – ArrSize;

}

}

if (Destindex < 0 )

{
while (Destindex ArrSize)

{

Destindex = Destindex + ArrSize;

}

}

return Destindex;

}

//_______________________________________________________//

void Solution()

{

//Declaring Arbitary Original Array And Copy

const int size = 700;

int ArrO[size];

int ArrC[size];

int Arrsize = 0;

//Pretaining to shifting

int Usershift;

int AbsoluteShift;

int Destinationindex;

//LCV
const int Sentinel = -999;

//Asking user to specify values and Computing Recquired Array Size

cout<<"\n\n\n\n\n";

cout<<"\tROTATE AN ARRAY \n\n\n";

cout<<"\t____________________________________________________________\n\n\n";

cout<<"\tPlease specify the array you would like to rotate. \n\n\tEnter -999 at the end of the array.\n\n";

cout<>ArrO[Arrsize],cout<<"\n";

while(ArrO[Arrsize] != Sentinel)

{

Arrsize++;

cout<>ArrO[Arrsize],cout<<"\n";

}

cout<>Usershift,cout<<"\n";

//Computing Absolute Shift

AbsoluteShift = AbsolShiftfunc (Usershift , Arrsize);

//Computing Shift

for (int Counter = 0; Counter < Arrsize ; Counter++)

{

Destinationindex = IndivShiftfunc (Counter , AbsoluteShift, Arrsize);

ArrC[Destinationindex] = ArrO[Counter];

}

//Displaying Original and Rotated Array

cout<<"\t* Orginal Array:_\n\n\t";

cout<<"\t\t[";

for (int Counter = 0; Counter < Arrsize ; Counter++)

{

cout<<ArrO[Counter]<<",";

}

cout<<"]\n\n\n";

cout<<"\t* Rotated Array:_\n\n\t";

cout<<"\t\t[";

for (int Counter = 0; Counter < Arrsize ; Counter++)

{

cout<<ArrC[Counter]<<",";

}

cout<<"]\n\n";

cout<<"\t____________________________________________________________\n\n\n\t";

}
//_________________________________________________________//

void main()

{

Solution();

}

//_________________________________________________________//

PS : i am a begginner so please dont bash me

22. […] “block swap” algorithms. Bentley also discusses a third algorithm, which he calls the “reversal” algorithm, and which we implemented several years ago. Bentley goes on to give timing comparisons […]