1

Is there an existing method that performs a left shift on a circular array of ints?

Specifically, given an array with 4 items {1,2,3,4} and a shift amount of 2, I would like a method that shifts the first two letters to the back of the array, making it appear like so: {3,4,1,2}.

Would this algorithm work to shift a circular array by one?

algShiftByOne(Array)
{
  temp=array[0];
  i=1
  while(i < Array.length - 1) // Loop from 1 up to array.length == last index
  {
    // If there is no exception i assume it copies value from
    // initial array starting from 1 up to array.length
    Array[i - 1] = Array[i];
    i++;
  }
 Array[Array.length]=temp;
}
Cory Klein
  • 51,188
  • 43
  • 183
  • 243
Sami
  • 11
  • 1
  • 3
  • 1
    Most likely. Such is the future of computer sciences. – luis.espinal Dec 15 '10 at 19:51
  • possible duplicate of [Fastest algorithm for circle shift N sized array for M position](http://stackoverflow.com/questions/876293/fastest-algorithm-for-circle-shift-n-sized-array-for-m-position) – Isaac Turner Sep 21 '15 at 15:46

7 Answers7

5

Here is my go at it... (here is an ideone.com demo)

import java.util.Arrays;

public class Test {

    public static void circularShiftLeft(int[] arr) {
        if (arr.length == 0)
            return;

        int first = arr[0];
        System.arraycopy(arr, 1, arr, 0, arr.length - 1);
        arr[arr.length - 1] = first;
    }

    public static void main(String[] arg) {
        int[] arr = { 1, 2, 3, 4 };
        System.out.println(Arrays.toString(arr));
        circularShiftLeft(arr);
        System.out.println(Arrays.toString(arr));
    }
}
aioobe
  • 413,195
  • 112
  • 811
  • 826
4

I had this one as an interview question. A simple in place (and somewhat intuitive) O(2n) solution for rotating m is to take the array, reverse it, then reverse the [0, m] and (m, n] subarrays. My solution, though a little less obvious, is inplace and O(n). Basically the idea is you rotate items forward one at a item, and eventually you will pass through all the elements. The catch is if the array is a multiple of the distance, which is where the GCD comes in. The following will do a rotate right, rotate left is left to the reader as an exercise:

public static void main(String[] args) {
    int[] f = {0, 4, 8, 2, 6, 7, 4, 5, 3};
    System.out.println(Arrays.toString(f));
    rotate(f, 3);
    System.out.println(Arrays.toString(f));
}

public static void rotate(int[] arr, int dist){
    int tmp, tmp2, gcd = GCD(arr.length, dist);
    for(int off=0;off<gcd;off++){
        tmp = arr[off];
        for(int i=0,idx=off;i<arr.length/gcd;idx=(idx+dist)%arr.length,i++){
            tmp2 = arr[(idx+dist)%arr.length];
            arr[(idx+dist)%arr.length] = tmp;
            tmp = tmp2;
        }
    }
}

public static int GCD(int a, int b) {
   if (b==0) return a;
   return GCD(b,a%b);
}
M. Jessup
  • 8,153
  • 1
  • 29
  • 29
  • I realize this, but wanted to point out that its is only half the operations. Admittedly negligible for small arrays, but it might make a difference if the arrays are large enough. – M. Jessup Dec 23 '10 at 17:02
0

Assuming that you want to shift by n:

  1. Copy the first n elements in an array named , for example, tempNumbers
  2. For each element from n to the last one, shift it to the left by n
  3. Copy the elements from tempNumbers to the end of the original array
thejh
  • 44,854
  • 16
  • 96
  • 107
0

Why don't you use a circular (doubly) linked list? In that case you only have to change your 'start pointer'.

Jochem
  • 2,995
  • 16
  • 18
  • Performance is fast (only changing start pointer). Costs in memory are relatively high of course. – Jochem Dec 15 '10 at 19:49
  • You are thinking of performance in terms of time (speed) only. There are also performance considerations in terms of space: for an array of N elements, a double-linked list built out of it will be of size `N(1+2M+B)` where M=size of pointer reference and B=space overhead of node structure containing the payload (the original element) and the pointers... and this is w/o counting the temporary space overhead of copying elements from the array into the list. This utterly complicated for such a simple algorithm. – luis.espinal Dec 15 '10 at 19:58
  • As I commented 'cost in memory is relatively high'. I think this is exactly your point? And concerning the 'complexity': yes it is more complex. The preferred solution would in my opinion depend on the usage (ie length of the list, intensity of shifting operations, etc) and demands (ie memory usage vs speed). – Jochem Dec 15 '10 at 20:09
  • Yep, that was my point (in addition that such things are not necessary in general.) Also, considering the maturity level of the question posted by the OP, the `preferred solution` should be one that shows classic algorithmic solutions. – luis.espinal Dec 15 '10 at 20:29
0

Here is some pseudo-code to do what you want.

Array shift(Array a, int shiftLength) {
    Array b;

    for(i = shiftLength; i < a.size(); i++)
        b.add(a.at(i));

    for(i = 0; i < shiftLength; i++)
        b.add(a.at(i));

    return b;
}
Cory Klein
  • 51,188
  • 43
  • 183
  • 243
  • 1
    `System.arraycopy()` is faster – thejh Dec 15 '10 at 19:50
  • @thejh Likely. Although I think this is still a good demonstration of how a circular shift is performed. – Cory Klein Dec 15 '10 at 19:57
  • @thejh - System.arrayCopy is not even applicable - by itself - for implementing `an arbitrary circular array n-shift` which is, by definition and efficiency, done `in place`. With System.arrayCopy, you need to copy N-n elements on a temporary array for performing a n-shift on a N-sized array. – luis.espinal Dec 15 '10 at 20:06
  • @Cory - You are creating N additional copies (or references). For a n-shift on a N-sized array, you `should not need` to create more than |N-n| additional copies (or references) on memory. – luis.espinal Dec 15 '10 at 20:09
  • @luis.espinal From the question: "method that takes the array then creates another array". This asker apparently could care less whether the operation was done in place. Although I agree that my solution is not exactly optimal. – Cory Klein Dec 15 '10 at 20:15
  • @luis.espinal You could make |N-n| copies and put them at the end of the array, then change the array pointer to the nth array item, but then what happens to the n*sizeof(int) bytes of memory at the beginning? What if you don't have n*sizeof(int) bytes of memory at the end of the array? You could shift everything down to make the space, but that's not very efficient either. – Cory Klein Dec 15 '10 at 20:21
0

This would shift the array a one to the left.

int[] a = new int[] { 1, 2, 3, 4, 5 };
int[] b = new int[a.length];
System.arraycopy(a, 1, b, 0, a.length - 1);
b[a.length - 1] = a[0];
// b = {2,3,4,5,1}
// edit
a = b;
Andreas Mohrhard
  • 187
  • 1
  • 8
  • 2
    *"This would shift the array a one to the left."* to be precise, it would leave the content of `a` unchanged ;) And btw, beware of the empty input array... – aioobe Dec 15 '10 at 20:09
0
public static void shift(int[] arr, int offs) {
    // e.g. arr = 1,2,3,4,5,6,7,8,9; offs = 3
    offs %= arr.length;
    offs = offs < 0 ? arr.length + offs : offs;

    if (offs > 0) {
        // reverse whole array (arr = 9,8,7,6,5,4,3,2,1)
        for (int i = 0, j = arr.length - 1; i < j; i++, j--)
            swap(arr, i, j);
        // reverse left part (arr = 7,8,9,6,5,4,3,2,1)
        for (int i = 0, j = offs - 1; i < j; i++, j--)
            swap(arr, i, j);
        // reverse right part (arr = 7,8,9,1,2,3,4,5,6)
        for (int i = offs, j = arr.length - 1; i < j; i++, j--)
            swap(arr, i, j);
    }
}

private static void swap(int[] arr, int i, int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}
Oleg Cherednik
  • 17,377
  • 4
  • 21
  • 35