Rotate array by arbitrary step size without creating second array

Question

So for a step size of 1, I want the array:

{1, 2, 3, 4}

To become:

{4, 1, 2, 3}

And for a step of size 2 the result will be:

{3, 4, 1, 2}

This is the code I'm using now:

private static int[] shiftArray(int[] array, int stepSize) {
  if (stepSize == 0)
     return array;

  int shiftStep = (stepSize > array.length ? stepSize % array.length : stepSize);

  int[] array2 = new int[array.length];
  boolean safe = false;
  for (int i = 0; i < array.length; i++) {
     if (safe) {
        array2[i] = array[i - shiftStep];
     }
     else {
        array2[i] = array[array.length - shiftStep + i];
        safe = (i+1) - shiftStep >= 0;
     }
  }
  return array2;
}

The code is working great, but is it possible to achieve this without creating a helper array (which is array2 in the code above)?

Thanks!

Answer 1

You can do it without creating as big an array:

// void return type as it shifts in-place
private static void shiftArray(int[] array, int stepSize) {
    // TODO: Cope with negative step sizes etc
    int[] tmp = new int[stepSize];
    System.arraycopy(array, array.length - stepSize, tmp, 0, stepSize);
    System.arraycopy(array, 0, array, stepSize, array.Length - stepSize);
    System.arraycopy(tmp, 0, array, 0, stepSize);
}

So for a 100,000 array and a step size of 10, it creates a 10-element array, copies the last 10 elements into it, copies the first 999,990 elements to be later, then copies from the temporary array back to the start of the array.

Answer 2

Use not the i++, but i += shiftSize and several loops (amount of them would be equal to gcd of array.length and shifSize).

Then you'll need only one int as buffer and execution time will be almost the same.

Answer 3

You could do it with a couple of loops, but its not easy. Using recursion is simpler in this case.

public static void main(String... args) {
    for (int i = 0; i < 12; i++) {
        int[] ints = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
        rotateLeft(ints, i);
        System.out.println(Arrays.toString(ints));
    }
}

public static void rotateLeft(int[] array, int num) {
    rotateLeft(array, num, 0);
}

private static void rotateLeft(int[] array, int num, int index) {
    if (index >= array.length) return;
    int tmp = array[(index + num) % array.length];
    rotateLeft(array, num, index + 1);
    array[index] = tmp;
}

prints

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
[2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 1]
[3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 1, 2]
[4, 5, 6, 7, 8, 9, 10, 11, 12, 1, 2, 3]
[5, 6, 7, 8, 9, 10, 11, 12, 1, 2, 3, 4]
[6, 7, 8, 9, 10, 11, 12, 1, 2, 3, 4, 5]
[7, 8, 9, 10, 11, 12, 1, 2, 3, 4, 5, 6]
[8, 9, 10, 11, 12, 1, 2, 3, 4, 5, 6, 7]
[9, 10, 11, 12, 1, 2, 3, 4, 5, 6, 7, 8]
[10, 11, 12, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[11, 12, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[12, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

Answer 4

Yes it's possible, you'd only need to temporary store one element additional to the array. Basically what you want to do is to:

1. store last element in tmp var
2. shift all elements to the right by one starting with the second to last element
3. sotre tmp var as first element
4. repeat from step 1 depending on your stepsize

Answer 5

This is not tested ...

public void rotateByStep(int[] array, int step) {
    step = step % array.length;
    if (step == 0) {
        return;
    }
    int pos = step;
    int tmp = array[0];
    boolean inc = array.length % step == 0;
    for (int i = 0; i < array.length; i++) {
        int tmp2 = array[pos];
        array[pos] = tmp;
        tmp = tmp2;
        pos = (pos + step) % array.length;
        if (inc && pos < step) {
            array[pos] = tmp;
            pos++;
            tmp = array[pos];
        }
    }
}

The idea I'm trying to implement is as follows:

• If step isn't a factor of length, then incrementing an index (pos) by step modulo length starting from zero will visit every array element once after length iterations.

• If step is a factor of length, then index (incremented as above) will get back to its starting point after length / step iterations. But if you then increment by one, you can process the cycle starting at 1, and then at 2, and so on. After length iterations, we'll have visited every array element once.

The rest is just rippling the element values as we cycle through the element indexes ... with some adjustment when we increment to the next cycle.

The other complete solutions have the advantage that they are much easier to understand, but this one requires no extra heap storage (i.e. no temporary array), and does the job in array.length loop iterations.

Answer 6

In n- 1 iterations

#include <stdio.h>

    int main(int argc, char **argv) {
        int k = 0, x = 0;
        int a[] = {-5,-4,-1,0,1,2,30,43,52,68,700,800,9999};
        int N = 0, R = 57; /*R = No of rotations*/
        int temp = 0, temp2  = 0, start = 0, iter = 0;

        x = 0;
        temp2 = a[x];

        N = sizeof(a) / sizeof(a[0]);
        for ( k = 0; k < N - 1; k++) {
            x = x + R;
            while ( x >= N ) {
                x = x - N;
            }
            temp = a[x];
            a[x] = temp2;
            temp2 = temp;
            if ( x == start ) {
                start = start + 1;
                x = x + 1;
                temp2 = a[x];
            }
            iter++;
        }
        a[start] = temp2;
        for ( k = 0; k < N; k++) {
            printf(" %d", a[k]);
        }
        printf("\n");
        printf("Done in %d iteration\n", iter);
        return 0;
    }