Fastest algorithm for circle shift N sized array for M position

algorithm arrays math puzzle programming-pearls
Arsen Mkrtchyan picture Arsen Mkrtchyan · May 18, 2009 · Viewed 31.4k times · Source

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

Jerry Penner picture Jerry Penner · May 18, 2009

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.

Related questions

Triplet whose sum in range (1,2)

Given n positive real numbers in an array, find whether there exists a triplet among this set such that, the sum of the triplet is in the range (1, 2). Do it in linear time and constant space. the array is not …

Read More
Find numbers of subarray of an array whose sum is divided by given number

I got stuck in one algorithm question. Please suggest me some efficient algorithm for the below problem. Question is Find numbers of subarrays whose sum is divisible by given number. My work I made one algorithm, whose complexity is O(…

Read More
How do I check if an array includes a value in JavaScript?

What is the most concise and efficient way to find out if a JavaScript array contains a value? This is the only way I know to do it: function contains(a, obj) { for (var i = 0; i < a.length; i++) { …

Read More