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.

Advertisements

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[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 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]
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s

%d bloggers like this: