CODEWITHSUNDEEP
javamethodsint
Sami
Sami

Reputation: 11

How do you perform a left shift on a circular array of ints?

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

Upvotes: 1

Views: 9959

Answers (7)

Oleg Cherednik
Oleg Cherednik

Reputation: 18253

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

Upvotes: 0

M. Jessup
M. Jessup

Reputation: 8222

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

Upvotes: 4

aioobe
aioobe

Reputation: 421340

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

Upvotes: 5

Andreas Mohrhard
Andreas Mohrhard

Reputation: 197

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;

Upvotes: 0

Cory Klein
Cory Klein

Reputation: 55910

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

Upvotes: 0

Jochem
Jochem

Reputation: 2993

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

Upvotes: 0

thejh
thejh

Reputation: 45578

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

Upvotes: 0

Related Questions