Can you rotate a vector in memory using minimal space and time?

Continuing from my study of Programming Pearls, this is a problem which occurs when you want to swap memory with time and space constraints. An example of this is in case of text drag and drop, where the lines of text have to be swapped quite efficiently.

The problem is specified as:

Rotate a one-dimensional vector of n elements left by i positions. For instance, with n=8 and i=3, the vector abcdefgh is rotated to defghabc. Simple code uses an n-element intermediate vector to do the job in n steps. Can you rotate the vector in time proportional to n using only a few dozen bytes of storage?

Let us analyze the possible ways to solve this problem.

Solution 1:

1. Copy the first i elements of the vector x to a temporary vector.
2. Move the remaining elements of the vector (i to n) left by i positions.
3. Copy the i elements from the temporary vector back to the end of the original vector x.
4. The vector x is now rotated left by i positions.

#define N 10

int copyrotate(char* vector, int i)
{
   char temp[N] = "";

   memcpy(temp, vector, i);
   memcpy(vector, &vector[i], N - i);
   memcpy(&vector[N-i], temp, i);
   return 0;
}

This method requires a temporary vector which should have a size equal to the original. Hence it is space expensive. One way to consume less space is to rotate the vector by one element at a time and call this i times. However this will make it time expensive (n x i times).

Solution 2:

This method is based on the concept that rotation of elements of a vector is nothing but the reversal of the parts of the vector. Suppose we need to rotate vector x left by i positions. This vector can be represented by ab where a is the range (0, i-1) and b is the range (i, n-1). The vector x can be rotated left by i positions as follows:

1. Reverse the part a of the vector containing the range (0, i-1).
2. Reverse the part b of the vector containing the range (i, n-1).
3. Now reverse the entire vector from (0, n-1).
4. The vector x is now rotated left by i positions.

#define N 10

int reverse(char* vector, int lower, int upper)
{
   char temp;
   while(lower < upper)
   {
      temp = vector[lower];
      vector[lower] = vector[upper];
      vector[upper] = temp;
      lower++;
      upper--;
   }
   return 0;
}

int reverserotate(char* vector, int i)
{
   reverse(vector, 0, i-1);
   reverse(vector, i, N-1);
   reverse(vector, 0, N-1);
   return 0;
}

This solution has the advantage that it rotates the vector proportional to n. So it has reduced time and space requirements.

You can find the implementations for both the solutions here.

It is mentioned that Brian Kernighan and P. J. Plauger used this code in their 1981 Software Tools in Pascal to move lines within a text editor which was much simpler and bug free than one based on linked lists.

Do you agree that the second solution uses minimal time and space for this problem?

Related Posts:

• Can you sort 10 million numbers using 1MB of memory?
• How To Install Google’s Go Programming Language
• The Ten Commandments for C++ Programmers
• The History Of Carriage Return Line Feed
• Three Pitfalls To Avoid When Using Dynamically Allocated Memory

Tags: programming, programs