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)
   {
    std::swap(t[from],t[to]);
    from++;
    to--;
   }
 }

////////////////////////////////////////
template <typename T>
void transpose(std::vector<T> & t,
               size_t pos)
 {
  reverse(t,0,pos-1);
  reverse(t,pos,t.size()-1);
  reverse(t,0,t.size()-1);
 }

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

*
* *

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:

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s

%d bloggers like this: