Fastest algorithm for circle shift N sized array for M position

by

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.

More Related Contents:

  1. The number prodigy : reverse sum of pattern
  2. Unique (non-repeating) random numbers in O(1)?
  3. Circle line-segment collision detection algorithm?
  4. How to create the most compact mapping n → isprime(n) up to a limit N?
  5. How do I calculate a point on a circle’s circumference?
  6. Fast permutation -> number -> permutation mapping algorithms
  7. Algorithm to detect intersection of two rectangles?
  8. What distribution do you get from this broken random shuffle?
  9. Finding a single number in a list [duplicate]
  10. Sort points in clockwise order?
  11. How do you calculate the average of a set of circular data? [closed]
  12. How do Trigonometric functions work? [closed]
  13. Precise subpixel line drawing algorithm (rasterization algorithm)
  14. Algorithm for finding similar images
  15. Why does this simple shuffle algorithm produce biased results?
  16. Mapping N-dimensional value to a point on Hilbert curve
  17. What’s a good algorithm to determine if an input is a perfect square? [duplicate]
  18. Floating Point Divider Hardware Implementation Details
  19. Combinations, Dispositions and Permutations in PHP
  20. Array remove duplicate elements
  21. nᵗʰ ugly number
  22. Unsupervised clustering with unknown number of clusters
  23. Calculate largest inscribed rectangle in a rotated rectangle
  24. Two Rectangles intersection
  25. Fastest primality test
  26. Efficient maths algorithm to calculate intersections
  27. Test if a number is fibonacci
  28. An inverse Fibonacci algorithm?
  29. what is the fastest way to find the gcd of n numbers?
  30. “Rounding” colour values to the nearest of a small set of colours

Leave a Comment