6

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!

Improve this question
7
  • I assume you don't want to return a copy and you want to alter the original? Commented Mar 9, 2012 at 14:13
  • 3
    You could use this method: stackoverflow.com/questions/4454072/… Commented Mar 9, 2012 at 14:15
  • Take a look at this for rearranging array elements in-place : stackoverflow.com/questions/1683020/… . Optimize the algorithm to rearrange specifically, in your case - circular shift. Commented Mar 9, 2012 at 14:19
  • stackoverflow.com/a/4464054/181772 is faster than anything posted here. it does just N moves, no matter what the shift distance and requires only constant size temp storage. Commented Mar 9, 2012 at 15:08
  • @andrewcooke I also thought it would be the fastest way to do the job, but my profiling shows that it's actually way slower than my method!! Jon's method is really really fast! I'll share the full results later. Commented Mar 9, 2012 at 15:29

6 Answers 6

Reset to default
12

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

12 Comments

The triple-reverse trick (mentioned in the questoin @assylias' linked to) can do it without any new array.
for the record, he is creating a helper array which is supposed to be avoided by the OPs question. ;) Nice solution anyway.
@stryba: Hence the first sentence - there's a big difference between creating an array which is as big as the initial array, and an array which is as big as the step size. I'm going for a practical approach...
@yshavit: Sure, you can do it without any new arrays. I'm sure there are multiple approaches that would cope. However, I strongly suspect they'd be more complicated and slower.
@JonSkeet This one's not that complicated at all, and though it may be a bit slower, it wouldn't be by much. Reversing an array in-place is pretty darn fast.
|
3

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.

Improve this answer

Comments

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]
Improve this answer

2 Comments

Ok you didn't create an array, but you used more space than the array would have
@harold indeed. I believe using a temporary array is likely to be the fastest solution. i.e. what was posted originally. Jon's solution might be slightly faster again.
2

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
Improve this answer

Comments

2

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.

Improve this answer

Comments

0

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;
    }
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.