Rotating Arrays (part II)

Last week we had a look at Kernighan’s algorithm to rotate an array k position and concluded that it might not be optimal, as each element was moved twice. This week, we’ll have a look at another algorithm that moves some items more than once, but overall will do less than two exchanges per items.

An algorithm (maybe due to Gries, found in his book The Science of Programming (1981)) will iteratively exchange the two largest portions of the array still to move. The algorithm will basically halve the size of the remaining portions, and, on the average, will move items less than twice.

Let’s have a look on the basic idea the algorithm exploits. Say we have an array containing the numbers 1 to 7 (for illustration purposes, the actual values are of no significance to the algorithm), and that we cant to exchange the first three with the last four (that’s equivalent to a rotation to the left of 3 or to a rotation to the right of 4). The algorithm witches the first three with the last three, and the last three are now in their final position. That leaves us with the sub-problem of rotating the first 4 items by one. The algorithm swaps again the largest out-of-place portion of the array, but this time it’s of size one. Once the swap is completed, it leaves us with the problem of rotating an array of size 3 by one; then of size two by one. Eventually the algorithm terminates when the arrays are of size one.

The above example is shown here with a diagram:

transpose

The implementation would be as follows:

template <typename T>
void exchange(std::vector<T> & t,
              size_t i,
              size_t j,
              size_t longueur)
 {
  for (size_t d=0;d<longueur;d++)
   std::swap(t[i+d],t[j+d]);
 }

////////////////////////////////////////
template <typename T>
void transpose(std::vector<T> & t,
               size_t pos)
 {
  size_t i=pos;
  size_t j=t.size()-pos;
  
  while (i!=j)
   {
    show(t);
    if (i>j)
     {
      exchange(t,pos-i,pos,j);
      i-=j;
     }
    else
     {
      exchange(t,pos-i,pos+j-i,i);
      j-=i;
     }
   }
  show(t);
  exchange(t,pos-i,pos,i);
 }

*
* *

This algorithm is much more complicated than Kernighan’s version, but is also much more efficient. The number of exchanges is \Theta(n), and the constant is small (the demonstration can be found in Gries’ book). This algorithm also progressively reduces the region of the array that is manipulated, and maybe we could use that to speed-up rotation of large arrays that do not fit in memory (i.e., lives on disk).

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: