Shifting elements in an array C++

Question

Hello,

I've developed a method called "rotate" to my stack object class. What I did was that if the stack contains elements: {0,2,3,4,5,6,7} I would needed to rotate the elements forwards and backwards.

Where if i need to rotate forwards by 2 elements, then we would have, {3,4,5,6,7,0,2} in the array. And if I need to rotate backwards, or -3 elements, then, looking at the original array it would be, {5,6,7,0,2,3,4}

So the method that I have developed works fine. Its just terribly ineffecient IMO. I was wondering if I could wrap the array around by using the mod operator? Or if their is useless code hangin' around that I havent realized yet, and so on.

I guess my question is, How can i simplify this method? e.g. using less code. :-)

void stack::rotate(int r)
{
    int i = 0;
    while ( r > 0 ) // rotate postively.
    {
     front.n = items[top+1].n;
        for ( int j = 0; j < bottom; j++ )
        {
            items[j] = items[j+1];                                  
        }
     items[count-1].n = front.n;
        r--;
    }

    while ( r < 0 )  // rotate negatively.
    {
     if ( i == top+1 )
     {
      front.n = items[top+1].n;  
      items[top+1].n = items[count-1].n; // switch last with first
     }

     back.n = items[++i].n; // second element is the new back
     items[i].n = front.n; 
     if ( i == bottom )
     {
            items[count-1].n = front.n; // last is first
            i = 0;  
            r++;   
      continue;
     }
     else
     {
            front.n = items[++i].n;
      items[i].n  = back.n;
            if ( i == bottom )
            {
                i = 0;
                r++; 
       continue;
            }
     }
    }
}

Answer 1

Instead of moving all the items in your stack, you could change the definition of 'beginning'. Have an index that represents the first item in the stack, 0 at the start, which you add to and subtract from using modular arithmetic whenever you want to rotate your stack.

Note that if you take this approach you shouldn't give users of your class access to the underlying array (not that you really should anyway...).

Answer 2

Well, as this is an abstraction around an array, you can store the "zero" index as a member of the abstraction, and index into the array based on this abstract notion of the first element. Roughly...

class WrappedArray
{
  int length;
  int first;
  T *array;

  T get(int index)
  {
    return array[(first + index) % length];
  }

  int rotateForwards()
  {
    first++;
    if (first == length)
      first = 0;
  }
}

Answer 3

You've gotten a couple of reasonable answers, already, but perhaps one more won't hurt. My first reaction would be to make your stack a wrapper around an std::deque, in which case moving an element from one end to the other is cheap (O(1)).

Answer 4

What you are after here is a circular list.
If you insist on storing items in an array just use top offset and size for access. This approach makes inserting elements after you reached allocated size expensive though (re-allocation, copying). This can be solved by using doubly-linked list (ala std::list) and an iterator, but arbitrary access into the stack will be O(n).

Answer 5

And now, the usual "it's already in Boost" answer: There is a Boost.CircularBuffer

Answer 6

If for some reason you'd prefer to perform actual physical rotation of array elements, you might find several alternative solutions in "Programming Pearls" by Jon Bentley (Column 2, 2.3 The Power of Primitives). Actually a Web search for Rotating Algorithms 'Programming Pearls' will tell you everything. The literal approach you are using now has very little practical value.

If you'd prefer to try to solve it yourself, it might help to try looking at the problem differently. You see, "rotating an array" is really the same thing as "swapping two unequal parts of an array". Thinking about this problem in the latter terms might lead you to new solutions :)

For example,

• Reversal Approach. Reverse the order of the elements in the entire array. Then reverse the two parts independently. You are done.

For example, let's say we want to rotate abcdefg right by 2

abcdefg -> reverse the whole -> gfedcba -> reverse the two parts -> fgabcde

P.S. Slides for that chapter of "Programming Pearls". Note that in Bentley's experiments the above algorithm proves to be quite efficient (among the three tested).

Answer 7

The function rotate below is based on reminders (do you mean this under the 'mod' operation?)

It is also quite efficient.

// Helper function.
// Finds GCD. 
// See http://en.wikipedia.org/wiki/Euclidean_algorithm#Implementations
int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);}

// Number of assignments of elements in algo is
// equal to (items.size() + gcd(items.size(),r)).
void rotate(std::vector<int>& items, int r) {
  int size = (int)items.size();
  if (size <= 1) return; // nothing to do
  r = (r % size + size) % size; // fits r into [0..size)
  int num_cycles = gcd(size, r);
  for (int first_index = 0; first_index < num_cycles; ++first_index) {
    int mem = items[first_index]; // assignment of items elements
    int index = (first_index + r) % size, index_prev = first_index;
    while (index != first_index) {
      items[index_prev] = items[index]; // assignment of items elements
      index_prev = index;
      index = (index + r) % size;
    };
    items[index_prev] = mem; // assignment of items elements
  }
}

Of course if it is appropriate for you to change data structure as described in other answers, you can obtain more efficient solution.

Answer 8

I don't understand what the variables front and back mean, and why you need .n. Anyway, this is the shortest code I know to rotate the elements of an array, which can also be found in Bentley's book.

#include <algorithm>

std::reverse(array    , array + r   );
std::reverse(array + r, array + size);
std::reverse(array    , array + size);