left rotate array in place C++

Vector rotation seems to be a particularly fertile ground for mysterious algorithms. Most of these can be found in the wild, with variations; all the efficient ones demand a bit of thought to understand their functioning.

If you were only rotating one element to the left, you can do it extremely efficiently:

template<typename Iter>
void rotate_one(Iter first, Iter last) {
  using Value = typename Iter::value_type;
  if (first != last) {
    Value temp = std::move(*first);
    for (Iter next = std::next(first);
         next != last;
         first = next, next = std::next(next)) 
      *first = std::move(*next);
    *first = std::move(temp);
  }
}

You could use that to rotate by delta positions by executing it Δ times (more accurately, Δ % N), but that takes time O(NΔ), which is effectively O(N²) for arbitrary Δ.

Although this solution is often shown as above, it is also possible to implement it without a temporary value object, using swaps instead of moves:

template<typename Iter>
void rotate_one(Iter first, Iter last) {
  if (first != last) {
    for (Iter next = std::next(first); next != last; ++first, ++next) 
      std::iterswap(first, next);
  }
}

Swap is usually a bit more work than a move, but it is possible that there is an efficient container-specific implementation of swap. In any case, this version will help to understand a later implementation.

A well-known and often cited O(N) solution is to do three reverses:

template<typename Iter>
void rotate_one(Iter first, Iter newfirst, Iter last) {
  std::reverse(first, newfirst);
  std::reverse(newfirst, last);
  std::reverse(first, last);
}

This is really elegant, in my opinion. You can see how it works by trying it on paper:

 a b ... c d w x ... y z 
 d c ... b a w x ... y z    first rotate
 d c ... b a z y ... x w    second rotate
 w x ... y z a b ... c d    third rotate

That's a special case of the well-known solution to "reverse the order of words in a sentence", which consists of first reversing the letters of each word, and then reversing the entire string.

However, it suffers from a couple of problems. First, it moves (almost) every element twice, when one move would be sufficient. Second, std::reverse requires a bidirectional iterator. There's nothing wrong with that, but it would be nicer for the algorithm to work with any forward iterator.

Another simple solution is to note that if you use the first algorithm but using an increment of Δ instead of one and wrap the iterators back to the beginning when they hit the end, then you will correctly rotate the vector if Δ and N are relatively prime. If they are not relatively prime, though, you will only have rotated some of the elements; the ones whose indices are 0 modulo gcd(N, Δ). To rotate the entire vector, you need to do this gcd(N, Δ) times, for each of the first gcd(N, Δ) elements in the vector.

Here's an illustration with 12 elements and a Δ of 3:

a b c d e f g h i j k l
 \    /     /     /
    \/     /     /
    /  \  /     /
   /     /\    /
  /     /    \/
 /     /     /  \
d b c g e f j h i a k l   first loop
   \    /     /     /
      \/     /     /
      /  \  /     /
     /     /\    /
    /     /    \/
   /     /     /  \
d e c g h f j k i a b l   second loop
     \    /     /     /
        \/     /     /
        /  \  /     /
       /     /\    /
      /     /    \/
     /     /     /  \
d e f g h i j k l a b c  third loop

This is easier with random access iterators (which is a defect); here's a sample implementation. (The variable count counts the number of elements which have been moved; every element is moved once, so when count reaches 0, the rotate is complete. This avoids having to compute the GCD to know how many times to run the outer loop.)

template<typename Container>
void rotate(Container& A, typename Container::size_type delta) {
  using Value = typename Container::value_type;
  using Index = typename Container::size_type;
  Index n = A.size();
  delta %= n;
  for (Index loop = 0, count = n;
       count; 
       ++loop, --count) {
    Index dst = loop;
    Value tmp = std::move(A[dst]);
    for (Index src = loop + delta;
         src != loop;
         --count, dst = src, src += (src < n - delta ? delta : delta - n))
      A[dst] = std::move(A[src]);
    A[dst] = std::move(tmp);
  }
}

As mentioned, that relies on the container having random access iterators.

Note that we could eliminate the need for the temporary storage by using swaps, as in the alternate version of the first algorithm above. If we do that, then we could just do all the outer loops in parallel, since they don't interfere with each other. So we could just move forward one element at a time, swapping each element with its Δ-next peer.

That leads to the tour-de-force provided as the sample implementation of std::rotate. It does exactly N swaps, which is possibly less slightly less efficient than the solution above (which does N + gcd(N, Δ) moves), but needs only forward iterators and swaps: (The code below is slightly modified to better conform with the above examples.)

template <class Iter>
void rotate(Iter first, Iter newfirst, Iter last) {
  if(first == newfirst || newfirst == last) return;

  Iter next = newfirst;
  do {
    std::iter_swap(first++, next++);
    if (first == newfirst) newfirst = next;
  } while (next != last);

  for(next = newfirst; next != last; ) {
    std::iter_swap(first++, next++);
    if (first == newfirst) newfirst = next;
    else if (next == last) next = newfirst;
  }
}

The only tricky part of the above is the handling of wraparound. Note that the (cyclic) distance between first and next is always the same (Δ). newfirst is used to track the wraparound point: every time first reaches newfirst, newfirst is advanced by Δ (by assigning it to the value of next, which is always Δ beyond first).

next wraps around the first time at the end of the first loop. Once that happens, it is within Δ of the end of the container; the second loop continues the swaps. In the process, it effectively computes the GCD of N and Δ with the Euclidean algorithm.

std::rotate() will do exactly what you need:

auto b = std::begin(A);
std::rotate( b, b + 2, std::end(A) );

It can be done after all.

What @ThomasMatthews suggests can work as a starting point: you can simply start swapping elements of array[i] and array[i+rotate], which works up to i=0...last-rotate. The issue is that the order of the last rotate number of elements is going to be hectic, unless the length of the array is an integer multiple of rotate, in which case it seems to be fine, though I do not know why (and this is just the first occurrence of that).
With this snippet you can interactively check how those elements will look like, and you will probably notice that the remaining elements need a length of array % rotate (that is the single number at the end) amount of right-shifting in order to become correct. Of course I do not know why.

function test(){
  var count=document.getElementById("count").valueAsNumber;
  var rotate=document.getElementById("rotate").valueAsNumber;
  var arr=[...Array(count).keys()];
  for(var i=0;i<count-rotate;i++){
    var t=arr[i];
    arr[i]=arr[i+rotate];
    arr[i+rotate]=t;    
  }
  document.getElementById("trivial").innerHTML=arr.slice(0,count-rotate).join();
  document.getElementById("tail").innerHTML=arr.slice(count-rotate).join();
  document.getElementById("remainder").innerHTML=count%rotate;
}
test();

<input type="number" id="count" oninput="test()" min="1" value="41"><br>
<input type="number" id="rotate" oninput="test()" min="1" value="12"><br>
<div id="trivial"></div>
<div id="tail"></div>
<div id="remainder"></div>

Then I just added some recursion, also using the fact that a right rotation can be done as a left-rotation (the shift amount has to be subtracted from the number of elements), so I do not have to write a separate method, because I am lazy. The chunks are displayed in separate lines (partial results are displayed normally, and the input chunks are in parentheses), so it is easier to follow. Here I use array.slice() which creates a new array, but it could be substituted by passing a start index and a length instead, so it could work as an in-place operation in C/C++.

function rot(arr,rotate){
  var retbase="("+rotate+":"+arr.join()+")<br>";    // input in parentheses
  for(var i=0;i<arr.length-rotate;i++){
    var t=arr[i];
    arr[i]=arr[i+rotate];
    arr[i+rotate]=t;
  }
  var rightrot=arr.length % rotate;                 // amount of right-rotation missing
  if(rightrot===0)                                  // done
    return retbase+arr.join();
  else{                                             // needs fixing
    retbase+=arr.slice(0,arr.length-rotate)+"<br>"; // partial result
    arr=arr.slice(arr.length-rotate);
    return retbase
      +rot(arr,arr.length-rightrot);                // flipping right-rotation left-rotation
  }
}
function test(){
  var count=document.getElementById("count").valueAsNumber;
  var rotate=document.getElementById("rotate").valueAsNumber;
  var arr=[...Array(count).keys()];
  document.getElementById("result").innerHTML=rot(arr,rotate);
}
test();

<input type="number" id="count" oninput="test()" min="1" value="41"><br>
<input type="number" id="rotate" oninput="test()" min="1" value="12"><br>
<div id="result"></div>

The depth/pattern of recursion has some resemblance to GCD calculations, so if someone has to say something about complexity, I would start looking that direction.

I tried a solution in O(n). Here I made another vector of same size. Suppose you want to left rotate by 2, so d = 2 here. First copy elements from position 2 to position 0 in new array up to the end. Then copy the elements from the start of first array to end of second i.e, from n-d position.

int i = 0;
int r = d;
vector<int> b(n);
for(i=0; i< n-d; i++)
{
    b[i] = a[r];
    r++;
}
r = 0;
for(i=n-d; i<n; i++)
{
    b[i] = a[r];
    r++;
}