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

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 2

Optimal solution

Question asked for fastest. Reversing three times is simplest but moves every element exactly twice, takes O(N) time and O(1) space. It is possible to circle shift an array moving each element exactly once also in O(N) time and O(1) space.

Idea

We can circle shift an array of length N=9 by M=1 with one cycle:

tmp = arr[0]; arr[0] = arr[1]; ... arr[7] = arr[8]; arr[8] = tmp; 

And if N=9, M=3 we can circle shift with three cycles:

1. tmp = arr[0]; arr[0] = arr[3]; arr[3] = tmp;
2. tmp = arr[1]; arr[1] = arr[4]; arr[4] = tmp;
3. tmp = arr[2]; arr[2] = arr[5]; arr[5] = tmp;

Note each element is read once and written once.

Diagram of shifting N=9, M=3

The first cycle is show in black with numbers indicating the order of operations. The second and third cycles are shown in grey.

The number of cycles required is the Greatest Common Divisor (GCD) of N and M. If the GCD is 3, we start a cycle at each of {0,1,2}. Calculating the GCD is fast with the binary GCD algorithm.

Example code:

// n is length(arr) // shift is how many place to cycle shift left void cycle_shift_left(int arr[], int n, int shift) {   int i, j, k, tmp;   if(n <= 1 || shift == 0) return;   shift = shift % n; // make sure shift isn't >n   int gcd = calc_GCD(n, shift);    for(i = 0; i < gcd; i++) {     // start cycle at i     tmp = arr[i];     for(j = i; 1; j = k) {       k = j+shift;       if(k >= n) k -= n; // wrap around if we go outside array       if(k == i) break; // end of cycle       arr[j] = arr[k];     }     arr[j] = tmp;   } } 

Code in C for any array type:

// circle shift an array left (towards index zero) // - ptr    array to shift // - n      number of elements // - es     size of elements in bytes // - shift  number of places to shift left void array_cycle_left(void *_ptr, size_t n, size_t es, size_t shift) {   char *ptr = (char*)_ptr;   if(n <= 1 || !shift) return; // cannot mod by zero   shift = shift % n; // shift cannot be greater than n    // Using GCD   size_t i, j, k, gcd = calc_GCD(n, shift);   char tmp[es];    // i is initial starting position   // Copy from k -> j, stop if k == i, since arr[i] already overwritten   for(i = 0; i < gcd; i++) {     memcpy(tmp, ptr+es*i, es); // tmp = arr[i]     for(j = i; 1; j = k) {       k = j+shift;       if(k >= n) k -= n;       if(k == i) break;       memcpy(ptr+es*j, ptr+es*k, es); // arr[j] = arr[k];     }     memcpy(ptr+es*j, tmp, es); // arr[j] = tmp;   } }  // cycle right shifts away from zero void array_cycle_right(void *_ptr, size_t n, size_t es, size_t shift) {   if(!n || !shift) return; // cannot mod by zero   shift = shift % n; // shift cannot be greater than n   // cycle right by `s` is equivalent to cycle left by `n - s`   array_cycle_left(_ptr, n, es, n - shift); }  // Get Greatest Common Divisor using binary GCD algorithm // http://en.wikipedia.org/wiki/Binary_GCD_algorithm unsigned int calc_GCD(unsigned int a, unsigned int b) {   unsigned int shift, tmp;    if(a == 0) return b;   if(b == 0) return a;    // Find power of two divisor   for(shift = 0; ((a | b) & 1) == 0; shift++) { a >>= 1; b >>= 1; }    // Remove remaining factors of two from a - they are not common   while((a & 1) == 0) a >>= 1;    do   {     // Remove remaining factors of two from b - they are not common     while((b & 1) == 0) b >>= 1;      if(a > b) { tmp = a; a = b; b = tmp; } // swap a,b     b = b - a;   }   while(b != 0);    return a << shift; } 

Edit: This algorithm may also have better performance vs array reversal (when N is large and M is small) due to cache locality, since we are looping over the array in small steps.

Final note: if your array is small, triple reverse is simple. If you have a large array, it is worth the overhead of working out the GCD to reduce the number of moves by a factor of 2. Ref: http://www.geeksforgeeks.org/array-rotation/