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.
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[1]) 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 aThe version with GCD is probably faster though as we only need to do one test each loop iteration.
[…] 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 […]
[…] 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 […]
#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: