DEV Community

loading...

Discussion on: Not an "Easy" Algorithm: Rotating an Array, Three Ways

Collapse
jakebman profile image
jakebman • Edited

There's also the reference implementation for C++'s rotate() method

It has the ability to rotate a smaller sub-section of an array as well. The array that started as [array[0], ... array[first], array[first+1], ..., array[middle], array[middle + 1], .... array[last -1] (array[last], which might be the magical just off the edge n+1th item), ...]
will become [array[0], ... array[middle], array[middle+1], ..., array[last -1], array[first], array[first + 1], .... (array[last], which is the first index that does not move), ...]

C++ has some non-javascriptisms, so let's a js transliteration:

function rotate (array, first, middle, last)
{
  next = middle;
  while (first!=next)
  {
    swap (array, first++, next++);
    if (next==last) next=middle;
    else if (first==middle) middle=next;
  }
}

// A well-known C++ library function. Simple implementation here.
function swap(arr, i, j){
  temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}