Rotating Arrays (Part I)

To “rotate” an array k position to the left (or to the right, doesn’t really matter) we could repeat k times a shift of one, using only one temporary variable. This method doesn’t use much auxiliary memory but is inefficient: it will do kn copies if we apply it to an array of size n. Surely we can do better.

A simple algorithm, proposed by Kernighan (again, as reported by Bentley in his books Programming Perls) consists in reversing parts of the array. Fortunately, reversing the contents of a part of an array is easy. It’s a \Theta(m) operation if the part is of length m. So Kernighan’s algorithm to rotate an array by k positions begins by reversing the first part of the array (from indices 0 to k-1), then reverses the second part (from indices k to n-1), and finally reverses the whole array again.


The implementation is straightforward:

template <typename T>
void reverse(std::vector<T> & t,
             size_t from,
             size_t to)
  while (from<to)

template <typename T>
void transpose(std::vector<T> & t,
               size_t pos)

If we look at a diagram of how the algorithm works, we would get something like this (the dashed line represents k):

* *

This algorithm is simple, easy to understand and elegant, but it is inefficient: it moves every item twice, once during the first reversal, and a second time during the whole array reversal. Is there a way to rotate an array while moving, on the whole, each item less than twice?

To be continued…

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: