Array Rotation
March 2, 2018
I’ve been re-reading Jon Bentley’s book Programming Pearls. In Chapter 2, Section 2.3, Bentley discusses the problem of rotating the elements of an array (for instance, rotate the array abcdefgh three positions left to defghabc) in time proportional to the length of the array using only a small, constant amount of extra space, and he gives three algorithms for doing so. Today’s exercise discusses the first. Here’s Bentley’s description:
One successful approach is a delicate juggling act; move x[0] to the temporary t, then move x[i] to x[0], x[2i] to x[i], and so on (taking all indices into x modulo n), until we come back to taking an element from x[0], at which point we instead take the element from t and stop the process. If that process didn’t move all the elements, then we start over at x[1], and continue until we move all the elements.
Then 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 Bentley’s array rotation algorithm. 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 
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: