Rotating an Array

by Zoran Horvat
August 16, 2014

Problem Statement

Given an array containing N integer numbers, rotate the array by M locations to the left (0 < M < N).

Example: Array 1, 2, 3, 4, 5 is given (N = 5). When rotated by two places to the left (M = 2), the array becomes 3, 4, 5, 1, 2.

Problem Analysis

If we look at the example, this problem boils down to swapping two segments of the array. Suppose that the array consists of segments A and B, so that the array looks like AB. Length of A is M – that is the part which will go to the end of the array after rotation. Then, rotating the array by M places turns it into BA.

One straight-forward way to solve the problem is to use spare space to store one part of the array while the other part is being moved. This method is presented in the picture below.

This solution would require M additional locations to store the front part of the array. Total number of copy operations per steps is M, N – M and M, which totals to N + M. One simple improvement is to use additional space for whichever part of the array is shorter. This means that in practice, M will never be larger than N/2. Worst case running time is thus 3N/2 and worst running space is N/2. In other words, this solution runs in O(N) time and O(N) space.

However, there is one better solution to this problem. Decades ago, additional space was often beyond limits to an application. Programmers had to come up with a more efficient solution, preferably the one that works in-place, i.e. uses O(1) additional space. Needless to say, O(N) running time was a must, knowing the CPU limitations of the time.

The idea that came up was brilliant in its simplicity. The root problem here is that the two parts of the array – AB – that we’re swapping are of unequal length. Now let’s assume that part A is shorter than B. We could represent B as two sub-arrays, so that the array becomes ACD. Segments C and D are selected so that D has the same length as A. Now it’s easy to replace A and D in-place, with only one additional memory location. As the result, we have transformed the array from ACD to DCA. This is not what we really wanted – we wanted CDA instead – but observe that A sub-array is now located at its final position. The problem has now been switched to the same problem on a shorter array. This time we need to replace D and C sub-arrays. Full sequence of steps is then: ACD -> DCA -> CDA, with recursive application of the algorithm to DC sub-array.

This solution obviously requires O(1) additional space, just to keep one temporary variable required to swap two sub-arrays of the same length. Time bound for this algorithm is easy to figure. Consider the first iteration when array ACD is transformed to DCA. Segment A of the array consists M elements and these elements are moved to the end of the array in exactly M swap operations, which requires exactly 3M variable assignment operations. After this step, elements in the A segment of the array are never touched again. Every part of the array which is moved in any of the subsequent recursive calls is never touched again. The process continues until complete array is exhausted. Sum of all segments moved until that moment is N elements because union of all segments is the whole array. Total number of variable assignments required for the task is 3N. This means that asymptotic complexity of the algorithm is O(N).

Implementation

In order to solve this problem, we first need to provide a routine which swaps two equally long subarrays. This routine will be used in each recursive step of the algorithm, and here it is:

            
function Swap(a, pos1, pos2, len)
    a - array
    pos1 - starting position of the first segment
    pos2 - starting position of the second segment
    len - length of each segment
begin
    for i = 1 to len
        begin
            tmp = a[pos1 + i - 1]
            a[pos1 + i - 1] = a[pos2 + i - 1]
            a[pos2 + i - 1] = tmp
        end
end
                
    

With this simple function at hand, we are ready to step to solving the real problem. Remember that the solution was to first swap segments on both ends of the array so that the array ACD is transformed into DCA. However, this statement was based on the presumption that segment A is not longer than CD. In other words, M <= N / 2.

The other case is when M > N / 2. In that case array AB is actually viewed as it consists of segments CDB. The first step is then to swap C and B, and only then to recursively invoke the rotation algorithm on the right-hand sub-array: CDB -> BDC -> BCD.

Code is the best documentation, so here is the solution. Keep on mind that algorithm below works on a one-based array, but that doesn't affect the function.

            
function RotateRecursive_Incomplete(a, pos, n, m)
    a - array
    pos - starting position
    n - length of the segment
    m - number of places to rotate to left
begin
    if m <= n / 2 then
        Swap(a, p, p + n - m, m)
        RotateRecursive(a, p, n - m, m)
    else
        Swap(a, p, p + m, n - m)
        RotateRecursive(a, p + n - m, m, 2 * m - n)
end
                
    

This solution covers both cases, but it has one terrible flaw - recursion never ends. We have to add the start and stop condition to the recursion in order to make it useful.

Starting is easy. We are starting with the whole array, which means pos=1, and n and m are actual parameters that represent length of the whole array and number of places to rotate.

Stopping the recursion is harder. When it doesn't make sense to make the next recursive call?

Can it happen that the sub-array is empty - the N argument to the recursive function to become zero? It could only happen if M is zero or equal to N. In the first call, that cannot happen. Subsequent calls might end up in that condition, but that case is not obvious right now.

Let's take a look at the second stopping condition, when number of places to rotate becomes zero. In that case, there is obviously nothing to do, and there will be nothing to do ever after. This happens in the else branch, when 2M = N. In that case, we have the array AB, with both segments being equally long. The whole work boils down to swapping them and getting the array BA. Rotation is finished and there is no point in calling the same function again because there is no sub-array which is not rotated well. Alternatively, it is possible that recursive call is made with N = M. Actually, this is the only case that can happen with previous implementation.

To conclude, it could happen that number of places to rotate (M) drops to zero or that N is reduced so that it becomes equal to M. When any of these conditions happens, the recursion unfolds and ends. This happens when M is exactly equal to half of the array length (2M = N), after which it makes no sense to continue calling the function further. Here is the corrected implementation:

            
function RotateRecursive1(a, pos, n, m)
    a - array
    pos - starting position
    n - length of the segment
    m - number of places to rotate to left
begin
    if 2 * m = n then
        Swap(a, pos, pos + m, m)
    else if 2 * m < n then
        Swap(a, pos, pos + n - m, m)
        RotateRecursive1(a, pos, n - m, m)
    else
        Swap(a, pos, pos + m, n - m)
        RotateRecursive1(a, pos + n - m, m, 2 * m - n)
end
                
    

This is the right recursive implementation. But now, observe that recursive call is the last statement in each execution branch. Local variables of the function play no role after the recursive call is made. This situation is known as tail recursion, and it is notorious of providing ground for replacing the recursion with iteration. Let me transform this recursive function first, and the solution will quickly become apparent:

            
function RotateRecursive(a, pos, n, m)
    a - array
    pos - starting position
    n - length of the segment
    m - number of places to rotate to left
begin

    pos2 = pos + n - m
    len = m
    if 2 * m > n then
        pos2 = pos + m
        len = n - m
    Swap(a, pos, pos2, len)

    if 2 * m <= n then
        n = n - m
    else
        pos = pos + n - m
        tmp = m
        m = 2 * m - n
        n = tmp

    if m > 0 and m < n then
        RotateRecursive(a, pos, n, m)

end
                
    

Now look what I've done. New solution recognizes that operation has two parts. First part is to call the Swap function with appropriate arguments, where arguments depend whether M breaches half of the array or not. The second part is to place the recursive call, again with modified arguments which depend on relation of M to half of the array length. Final touch is to recognize that recursive call is placed only if there is something to do.

This implementation can easily be transformed into iteration by simply wrapping it into a loop and letting the body of the loop adapt parameters for the iteration that follows. That is exactly what compilers which are capable to recognize tail recursion do. Here is the solution:

            
function Rotate(a, pos, n, m)
    a - array
    pos - starting position
    n - length of the segment
    m - number of places to rotate to left
begin

    while m > 0 and m < n
        begin

            pos2 = pos + n - m
            len = m
            if 2 * m > n then
                pos2 = pos + m
                len = n - m
            Swap(a, pos, pos2, len)

            if 2 * m <= n then
                n = n - m
            else
                pos = pos + n - m
                tmp = m
                m = 2 * m - n
                n = tmp

        end

end
                
    

It's all the same - only the recursive call is missing. If statement that preceded the recursive call is now replaced with the while loop condition testing. And the execution of the recursive call itself is replaced by the next iteration of the loop. This solution is probably harder to understand than the recursive implementation, but it is somewhat more efficient.

Finally, here is the C# implementation of the solution:

using System;

namespace RotatingArray
{
    class Program
    {

        private static int[] InitializeArray(int n)
        {
            int[] a = new int[n];
            for (int i = 0; i < a.Length; i++)
                a[i] = i;
            return a;
        }

        private static void Print(int[] a)
        {
            foreach (int x in a)
                Console.Write("{0:00} ", x);
            Console.WriteLine();
        }

        private static void Swap(int[] a, int pos1, int pos2, int len)
        {
            for (int i = 0; i < len; i++)
            {
                int tmp = a[pos1 + i];
                a[pos1 + i] = a[pos2 + i];
                a[pos2 + i] = tmp;
            }
        }

        private static void RotateRecursive(int[] a, int pos, int n, int m)
        {

            int pos2 = pos + n - m;
            int len = m;
            if (2 * m > n)
            {
                pos2 = pos + m;
                len = n - m;
            }
            Swap(a, pos, pos2, len);

            if (2 * m <= n)
            {
                n -= m;
            }
            else
            {
                pos += n - m;
                int tmp = m;
                m = 2 * m - n;
                n = tmp;
            }

            if (m > 0 && m < n)
                RotateRecursive(a, pos, n, m);

        }

        private static void Rotate(int[] a, int pos, int n, int m)
        {
            while (m > 0 && m < n)
            {
                int pos2 = pos + n - m;
                int len = m;
                if (2 * m > n)
                {
                    pos2 = pos + m;
                    len = n - m;
                }
                Swap(a, pos, pos2, len);

                if (2 * m <= n)
                {
                    n = n - m;
                }
                else
                {
                    pos += n - m;
                    int tmp = m;
                    m = 2 * m - n;
                    n = tmp;
                }

            }
        }

        static void Main(string[] args)
        {
            while (true)
            {
                Console.Write("Enter N (0 to exit): ");
                int n = int.Parse(Console.ReadLine());
                if (n <= 0)
                    break;

                Console.Write("Enter M: ");
                int m = int.Parse(Console.ReadLine());

                int[] a = InitializeArray(n);
                Print(a);

                Rotate(a, 0, a.Length, m);

                Print(a);
                Console.WriteLine();

            }
        }

    }
}

Demonstration

When console application listed above is run, it produces the following output:

            
Enter N (0 to exit): 10
Enter M: 3
00 01 02 03 04 05 06 07 08 09
03 04 05 06 07 08 09 00 01 02

Enter N (0 to exit): 17
Enter M: 11
00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16
11 12 13 14 15 16 00 01 02 03 04 05 06 07 08 09 10

Enter N (0 to exit): 0
                
    

Follow-Up Exercises

As an exercise, think about what it takes to rotate the array to the right?

---