## 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$):

*
* *

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…