## Array Rotation

### March 2, 2018

I found myself confused by Bentley’s description; Bentley didn’t seem to be his normal good self at explaining the algorithm. I even looked at his solution, and it still took a while for the algorithm to sink into my brain. Here is Bentley’s code to rotate x[n] left by rotdist:

```for i = (0, gcd(rotdist, n))
/* move i-th values of blocks */
t = x[i]
j = i
loop
k = j + rotdist
if k >= n
k -= n
if k == i
break
x[j] = x[k]
j = k
x[j] = t```

That infinite loop that breaks in the middle confused me for a moment, until I rewrote Bentley’s algorithm like this:

```for i = (0, gcd(rotdist, n))
t = x[i]
j = i
k = j + rotdist
k -= n if k >= n
while k <> i
x[j] = x[k]
j = k
k = j + rotdist
k -= n if k >= n
x[j] = t```

Bentley breaks the loop in the middle to avoid rewriting the calculation of k, and uses `if` and a subtraction instead of the modulo operator. Here is my version of Bentley’s algorithm, with the modulo operator, descriptive variable names, and lo and hi updated in parallel:

```function rotate(ary, len, dist)
for idx from 0 to gcd(dist, len)
temp = ary[idx]
lo, hi = idx, (idx + dist) % len
while hi <> idx
ary[lo] = ary[hi]
lo, hi = hi, (hi + dist) % len
ary[lo] = temp
return ary```

That’s clearer to me, and hopefully to you, too. The `gcd` is interesting. If len and dist are coprime, the `while` will visit every element of the array and the loop on idx will be executed only once; otherwise, the loop on idx will have to execute once for each cycle to be permuted. Here’s a working version in Scheme:

```(define (rotate ary len dist)
(do ((idx 0 (+ idx 1))) ((= idx (gcd dist len)) ary)
(let ((temp (vector-ref ary idx)))
(do ((lo idx hi) (hi (modulo (+ idx dist) len) (modulo (+ hi dist) len)))
((= hi idx) (vector-set! ary lo temp))
(vector-set! ary lo (vector-ref ary hi))))))```

And here’s an example:

```> (rotate '#(a b c d e f g h) 8 3)
#(d e f g h a b c)```

You can run the program at https://ideone.com/19NYmq.

Pages: 1 2

### 5 Responses to “Array Rotation”

1. matthew said

We can do this without explicitly calculating the GCD: just cycle round from 0, then from 1, and so on until the right number of elements have been moved.

No doubt more cache-friendly solutions will be considered in the future exercises.

```import sys
n = int(sys.argv)
for m in range(n+1):
a = list(range(n))
j,k = 0,0
for i in range(n):
j1 = (j+m)%n;
if j1 == k: k = k+1; j = k
else: a[j],a[j1] = a[j1],a[j]; j = j1
print a
```
```\$ python r.py 12
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 0]
[2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 0, 1]
[3, 4, 5, 6, 7, 8, 9, 10, 11, 0, 1, 2]
[4, 5, 6, 7, 8, 9, 10, 11, 0, 1, 2, 3]
[5, 6, 7, 8, 9, 10, 11, 0, 1, 2, 3, 4]
[6, 7, 8, 9, 10, 11, 0, 1, 2, 3, 4, 5]
[7, 8, 9, 10, 11, 0, 1, 2, 3, 4, 5, 6]
[8, 9, 10, 11, 0, 1, 2, 3, 4, 5, 6, 7]
[9, 10, 11, 0, 1, 2, 3, 4, 5, 6, 7, 8]
[10, 11, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[11, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
```
2. matthew said

The version with GCD is probably faster though as we only need to do one test each loop iteration.

3. […] Bentley gives three O(n) algorithms for rotating an array. We looked at the first algorithm in the previous exercise; today we look at the second […]

4. […] of Jon Bentley’s book Programming Pearls in the last two exercises, and have implemented his “juggling” and “block swap” algorithms. Bentley also discusses a third algorithm, which he calls […]

5. Daniel said
```#include <stdio.h>
#include <stdlib.h>

void print_array(char* array, size_t n) {
printf("[");
for (size_t i = 0; i < n; ++i) {
if (i > 0) printf(", ");
printf("%c", array[i]);
}
printf("]\n");
}

void rotate(char* array, size_t n, size_t i) {
if (n == 0) return;
size_t n_moved = 0;
size_t start_idx = 0;
while (1) {
char tmp = array[start_idx];
size_t dest_idx = start_idx;
size_t source_idx = (start_idx + i) % n;
while (1) {
++n_moved;
if (source_idx == start_idx) {
array[dest_idx] = tmp;
break;
}
array[dest_idx] = array[source_idx];
dest_idx = source_idx;
source_idx = (source_idx + i) % n;
}
if (n_moved == n) break;
++start_idx;
}
}

int main(void) {
char array[] = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'};
size_t n = sizeof(array) / sizeof(char);
printf("array:\n  ");
print_array(array, n);
rotate(array, n, 3);
printf("rotate(array, 3)\n  ");
print_array(array, n);
return EXIT_SUCCESS;
}
```

Output:

```array:
[a, b, c, d, e, f, g, h]
rotate(array, 3)
[d, e, f, g, h, a, b, c]
```