Fastest algorithm for circle shift N sized array for M position

Question

What is the fastest algorithm for circle shifting array for m positions?
For example [3 4 5 2 3 1 4] shift m = 2 positions should be [1 4 3 4 5 2 3]

Thanks a lot

Answer 1

Set it up with pointers, and it takes almost no time. Each element points to the next, and the "last" (there is no last; after all, you said it was circular) points to the first. One pointer to the "start" (first element), and maybe a length, and you have your array. Now, to do your shift, you just walk your start pointer along the circle.

Ask for a good algorithm, and you get sensible ideas. Ask for fastest, and you get weird ideas!

Answer 2

Depending on the data structure you use, you can do it in O(1). I think the fastest way is to hold the array in the form of a linked list, and have a hash table that can translate between "index" in the array to "pointer" to the entry. This way you can find the relevant heads and tails in O(1), and do the reconnection in O(1) (and update the hash table after the switch in O(1)). This of course would be a very "messy" solution, but if all you're interested in is the speed of the shift, that will do (on the expense of longer insertion and lookup in the array, but it will still remain O(1))

If you have the data in a pure array, I don't think you can avoid O(n).

Coding-wise, it depends on what language you are using.

In Python for example, you could "slice" it (assume n is the shift size):

result = original[-n:]+original[:-n]

(I know that hash lookup is in theory not O(1) but we're practical here and not theoretical, at least I hope so...)

Answer 3

It's just a matter of representation. Keep the current index as an integer variable and when traversing the array use modulo operator to know when to wrap around. Shifting is then only changing the value of the current index, wrapping it around the size of the array. This is of course O(1).

For example:

int index = 0;
Array a = new Array[SIZE];

get_next_element() {
    index = (index + 1) % SIZE; 
    return a[index];
}

shift(int how_many) {
    index = (index+how_many) % SIZE;
}

Answer 4

If you want O(n) time and no extra memory usage (since array was specified), use the algorithm from Jon Bentley's book, "Programming Pearls 2nd Edition". It swaps all the elements twice. Not as fast as using linked lists but uses less memory and is conceptually simple.

shiftArray( theArray, M ):
    size = len( theArray )
    assert( size > M )
    reverseArray( theArray, 0, size - 1 )
    reverseArray( theArray, 0, M - 1 )
    reverseArray( theArray, M, size - 1 )

reverseArray( anArray, startIndex, endIndex ) reverses the order of elements from startIndex to endIndex, inclusive.

Answer 5

Keep two indexes to the array, one index starts from beginning of the array to the end of array. Another index starts from the Mth position from last and loops through the last M elements any number of times. Takes O(n) at all times. No extra space required.

circleArray(Elements,M){
 int size=size-of(Elements);

 //first index
 int i1=0;

 assert(size>M)

 //second index starting from mth position from the last
 int i2=size-M;

 //until first index reaches the end
 while(i1<size-1){

  //swap the elements of the array pointed by both indexes
  swap(i1,i2,Elements);

  //increment first pointer by 1
  i1++;

  //increment second pointer. if it goes out of array, come back to
  //mth position from the last
  if(++i2==size) i2=size-M;

 }
}

Answer 6

circelArray has some errors and is not working in all cases! :/ EDIT: loop must continue while i1 < i2 NOT i1 < last - 1

void Shift(int* _array, int _size, int _moves)
{
    _moves = _size - _moves;
    int i2 = _moves;
         int i1 = -1;
         while(++i1 < i2)
    {
     int tmp = _array[i2];
     _array[i2] = _array[i1];
     _array[i1] = tmp;
     if(++i2 == _size) i2 = _moves;
    }
}

THIS WORKS! :) 0xDEAD BEEF