2

Is this linear complexity implementation of circular array rotation correct?

n = number of elements k = number of rotations

    int write_to     = 0;
    int copy_current = 0;
    int copy_final   = a[0];
    int rotation     = k;
    int position     = 0;

    for (int i = 0; i < n; i++) {
        write_to     = (position + rotation) % n;
        copy_current = a[write_to];
        a[write_to]  = copy_final;
        position     = write_to;
        copy_final   = copy_current;
     }
ankit409
  • 93
  • 7
  • Well, the complexity is certainly linear. But if you expect this to rotate the values in the array by shifting them all by `#rotation` positions, what's traditionally described as a circular rotation, you're going be surprised when this is not what you will end up with. – Sam Varshavchik Mar 05 '17 at 02:27
  • http://stackoverflow.com/questions/11893053/circular-left-shift-of-an-array-by-n-positions-in-java – vadim Mar 05 '17 at 02:28
  • 2
    @vadim: The accepted answer to that question is certainly correct but a prettier solution is: 1. Reverse the first k elements. 2. Reverse the rest of the elements. 3. Reverse the entire array. (All the reverses are in-place.) – rici Mar 05 '17 at 03:39
  • yes. I like it! :) – vadim Mar 05 '17 at 03:45
  • Related language agnostic: https://stackoverflow.com/questions/876293/fastest-algorithm-for-circle-shift-n-sized-array-for-m-position – Ciro Santilli OurBigBook.com Mar 18 '21 at 15:49

3 Answers3

0

No.

Consider this example.

#include <iostream>

int main(void) {
    int n = 6;
    int k = 2;
    int a[] = {1, 2, 3, 4, 5, 6};

    int write_to     = 0;
    int copy_current = 0;
    int copy_final   = a[0];
    int rotation     = k;
    int position     = 0;

    for (int i = 0; i < n; i++) {
        write_to     = (position + rotation) % n;
        copy_current = a[write_to];
        a[write_to]  = copy_final;
        position     = write_to;
        copy_final   = copy_current;
     }

    for (int i = 0; i < n; i++) {
        std::cout << a[i] << (i + 1 < n ? ' ' : '\n');
    }
    return 0;
}

Expected result:

5 6 1 2 3 4

Actual result:

3 2 1 4 1 6
MikeCAT
  • 73,922
  • 11
  • 45
  • 70
0

Using stl::rotate on std::array, you can left rotate by, say 2, as:

std::array<int, 6> a{1, 2, 3, 4, 5, 6};
std::rotate(begin(a), begin(a) + 2, end(a)); // left rotate by 2

to yield: 3 4 5 6 1 2, or right-rotate by, say 2, as:

std::rotate(begin(a), end(a) - 2, end(a)); // right rotate by 2

to yield: 5 6 1 2 3 4, with linear complexity.

srinivirt
  • 286
  • 1
  • 6
0

Rotate an Array of length n for k times in left or right directions.

The code is in Java

I define a Direction Enum:

public enum Direction {
    L, R
};

Rotation with times and direction:

public static final void rotate(int[] arr, int times, Direction direction) {
    if (arr == null || times < 0) {
        throw new IllegalArgumentException("The array must be non-null and the order must be non-negative");
    }
    int offset = arr.length - times % arr.length;
    if (offset > 0) {
        int[] copy = arr.clone();
        for (int i = 0; i < arr.length; ++i) {
            int j = (i + offset) % arr.length;
            if (Direction.R.equals(direction)) {
                arr[i] = copy[j];
            } else {
                arr[j] = copy[i];
            }
        }
    }
}

Complexity: O(n).

Example: Input: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] Rotate 3 times left Output: [4, 5, 6, 7, 8, 9, 10, 1, 2, 3]

Input: [4, 5, 6, 7, 8, 9, 10, 1, 2, 3] Rotate 3 times right Output: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Sabuj Das
  • 31
  • 4
  • While this may answer the question, it is better to explain the essential parts of the answer and possibly what was the problem with OPs code. – pirho Dec 04 '17 at 20:03
  • You did not answer the question ('Is this linear complexity implementation of circular array rotation correct?') but just present your solution to the underlying problem without any comment. It is always appreciated if you explain why and what. – fragmentedreality Dec 04 '17 at 20:05