Exercise #28: Rotating an Array by Zoran Horvat @zoranh75 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 straightforward 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 inplace, 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 subarrays, 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 inplace, 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 subarray 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 subarrays. Full sequence of steps is then: ACD > DCA > CDA, with recursive application of the algorithm to DC subarray.
This solution obviously requires O(1) additional space, just to keep one temporary variable required to swap two
subarrays 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 righthand
subarray: CDB > BDC > BCD.
Code is the best documentation, so here is the solution. Keep on mind that
algorithm below works on a onebased 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 subarray 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 subarray 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
FollowUp Exercises
As an exercise, think about what it takes to rotate the array to the right?
See also:
Published: Aug 16, 2014
ZORAN HORVAT Zoran is software architect dedicated to clean design and CTO in a growing software company. Since 2014 Zoran is an author at Pluralsight where he is preparing a series of courses on objectoriented and functional design, design patterns, writing unit and integration tests and applying methods to improve code design and longterm maintainability. Follow him on Twitter @zoranh75 to receive updates and links to new articles. Watch Zoran's video courses at pluralsight.com (requires registration): Making Your C# Code More ObjectOriented This course will help leverage your conceptual understanding to produce proper objectoriented code, where objects will completely replace procedural code for the sake of flexibility and maintainability. More... Advanced Defensive Programming Techniques This course will lead you step by step through the process of developing defensive design practices, which can substitute common defensive coding, for the better of software design and implementation. More... Tactical Design Patterns in .NET: Creating Objects This course sheds light on issues that arise when implementing creational design patterns and then provides practical solutions that will make our code easier to write and more stable when running. More... Tactical Design Patterns in .NET: Managing Responsibilities Applying a design pattern to a realworld problem is not as straightforward as literature implicitly tells us. It is a more engaged process. This course gives an insight to tactical decisions we need to make when applying design patterns that have to do with separating and implementing class responsibilities. More... Tactical Design Patterns in .NET: Control Flow Improve your skills in writing simpler and safer code by applying coding practices and design patterns that are affecting control flow. More... Writing Highly Maintainable Unit Tests This course will teach you how to develop maintainable and sustainable tests as your production code grows and develops. More... Improving Testability Through Design This course tackles the issues of designing a complex application so that it can be covered with high quality tests. More... Share this article
