Remembering How to Rotate an Array

For no reason that I can remember, I was recently reminded of a solution to a homework problem way back from my first semester in college that I thought was creative. Having not had anything to say here for four months, I thought it would be fun to dig up the code and take a look.

The challenge was to rotate a vector in place using constant extra memory and less than O(n²) moves. There was very little additional information. I remember scratching my head for a while and then coming up with this crazy scheme involving the greatest common divisor which I drew out in great detail with boxes and arrows explaining how everything would move. I was disgusted that I couldn't arrive at a way to remove the gcd function entirely.

Now that I look, I see it is an early problem in book Programming Pearls. Their solutions can be found ​here. Algorithm 3 is the closest to mine, and they indeed don't need to calculate the gcd ahead of time.

Oh, and I was sloppy with whitespace and some other details back then.

/* Euclid's algorithm for calculating the greatest common divisor of two numbers.
        Taken from page 58 of "Data Structures & Algorithm Analysis in C++ Second Edition" by Mark Allen Weiss. */
int gcd(int a, int b)
{
        while (b)
        {
                int r = a % b;
                a = b;
                b = r;
        }

        return a;
}

/* Rotates a vector i steps, using minimal moves.
        This requires an "extra" calculation of the greatest common divisor of i and v.size(), but this algorithm
        still wins out over rotating v one element at a time i times, because this is O(n) while the latter method is O(n^2) */
template<class T> void rotate(vector<T> &v, int i)
{
        int size = v.size();
        int factor = gcd(size, i);
        i %= size;

        int p;

        for (p = 0; p < factor; p++)
        {
                int n;
                T temp = v[p];  // Pull out one element so we can shift everything forward.
                for (n = (p + i) % size; n != p; n = (n + i) % size)    // Until we get back to where we start, shift each element forward.
                        v[(n - i + size) % size] = v[n];
                        
                v[(p - i + size) % size] = temp;        // Put back original element.
        }
}

AddComment