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.

Advertisements

Pages: 1 2