Programming Praxis

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.

Pages: 1 2