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.
Programming Praxis 
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) v (begin (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)) vec (let ((e (- n d))) (if (<= d e) (begin (vector-swap-disjoint-ranges! vec d start (- end d)) (vector-range-rotate-left! vec d start (+ start e))) (begin (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)) (newline) (f (+ d 1)))))) (test)Minor point: The tests included in the solution by @programmingpraxis
mutate literal vectors, which I believe is forbidden by standard
Scheme.
[…] 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” […]
Here’s a solution in C.
#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"); } static void swap(char* a1, char* a2, size_t n) { for (size_t i = 0; i < n; ++i) { char tmp = a1[i]; a1[i] = a2[i]; a2[i] = tmp; } } void rotate(char* array, size_t n, size_t i) { i %= n; while (1) { if (n <= 1 || i == 0) break; if (i == n - i) { swap(array, array + i, i); break; } else if (i < n - i) { swap(array, array + n - i, i); n -= i; } else { swap(array, array + i, n - i); array += n - i; size_t n_ = n; n = i; i -= n_ - i; } } } int main(void) { char array[] = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'}; size_t n = sizeof(array) / sizeof(char); print_array(array, n); rotate(array, n, 3); print_array(array, n); return EXIT_SUCCESS; }Output: