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]