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.
The 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 […]
Output: