Reputation: 5475

Rotate array by arbitrary step size without creating second array

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!

Upvotes: 6

Answers (6)

Alam

Reputation: 1596

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;
    }

Upvotes: 0

Jon Skeet

Reputation: 1499860

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.

Upvotes: 12

Stephen C

Reputation: 718718

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.

Upvotes: 2

Peter Lawrey

Reputation: 533472

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]

Upvotes: 3