Array Rotation, Again

March 6, 2018

In Section 2.3 of his book Programming Pearls, Jon 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 algorithm:

A different algorithm results from a different view of the problem: rotating the vector x is really just swapping the two segments of the vector ab to be the vector ba, where a represents the first i elements of x. Suppose a is shorter than b. Divide b into bl and br, so that br is the same length as a. Swap a and br to transform abrbr into brbla. The sequence a is in its final place, so we can focus on swapping the two parts of b. Since this new problem has the same form as the original, we can solve it recursively. This algorithm can lead to an elegant program, but it requires delicate code and some thought to see that it is efficient enought.

As before, Bentley challenges us to implement the rotation algorithm and he gives a cryptic hint: “How does the greatest common divisor of i and n appear in the program?”

Your task is to implement the array rotation algorithm described above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.


Pages: 1 2

3 Responses to “Array Rotation, Again”

  1. chaw said

    Here is an implementation in standard R7RS Scheme.

    (import (scheme base)
            (scheme write))
    (define (vector-swap! v i j)
      (let ((t (vector-ref v i)))
        (vector-set! v i (vector-ref v j))
        (vector-set! v j t)))
    ;; [start1, ..., start1+n-1] and [start2, ..., start2+n-1] must be disjoint.
    ;; TODO? handle non-disjoint cases too.
    (define (vector-swap-disjoint-ranges! v n start1 start2)
      (if (<= n 0)
            (vector-swap! v start1 start2)
            (vector-swap-disjoint-ranges! v (- n 1) (+ start1 1) (+ start2 1)))))
    ;; left-rotate vec[start..end-1] by steps positions.
    ;; negative steps => rotate -steps right
    (define (vector-range-rotate-left! vec steps start end)
      (let* ((n (- end start))
             (d (floor-remainder steps n)))
        (if (or (zero? d)
                (< n 2))
            (let ((e (- n d)))
              (if (<= d e)
                    (vector-swap-disjoint-ranges! vec d start (- end d))
                    (vector-range-rotate-left! vec d start (+ start e)))
                    (vector-swap-disjoint-ranges! vec e start (- end e))
                    (vector-range-rotate-left! vec (- d e) (+ start e) end)))))))
    (define (vector-rotate-left! vec steps)
      (vector-range-rotate-left! vec steps 0 (vector-length vec)))
    (define (test)
      (let ((v '#(0 1 2 3 4 5 6 7 8 9)))
        (let f ((d -12))
          (when (<= d 12)
            (display d)
            (display (vector-rotate-left! (vector-copy v) d))
            (f (+ d 1))))))

  2. chaw said

    Minor point: The tests included in the solution by @programmingpraxis
    mutate literal vectors, which I believe is forbidden by standard

  3. […] 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 the “reversal” […]

Leave a Reply

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

You are commenting using your 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 )

Google+ photo

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

Connecting to %s

%d bloggers like this: