## 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

xis really just swapping the two segments of the vectorabto be the vectorba, wherearepresents the firstielements ofx. Supposeais shorter thanb. Dividebintoband_{l}b, so that_{r}bis the same length as_{r}a. Swapaandbto transform_{r}abinto_{r}b_{r}b. The sequence_{r}b_{l}aais in its final place, so we can focus on swapping the two parts ofb. 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

Here is an implementation in standard R7RS Scheme.

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.

Output: