How do you do a left shift in a circular ints array?

Question

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

In particular, if you specify an array with 4 elements {1,2,3,4} and a shift value of 2, I need a method that shifts the first two letters to the back of the array, doing this as follows: {3,4,1,2} .

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

Answer 1

Here is my move ... (here is a demo of ideone.com )

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

Answer 2

I had this question as an interview. A simple in place (and somewhat intuitive) O (2n) solution for rotating m is to capture the array, reverse it, then reverse the subarrays [0, m] and (m, n]. My solution, although a little less obvious, is inplace and O (n) Basically, the idea is that you rotate the elements forward one at a time in the element, and eventually you will go through all the elements.The trick is an array that is a multiple of the distance, where the GCD appears: turn right, turn left for the reader remains in the form of 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); } 

Answer 3

Assuming you want to shift by n :

• Copy the first n elements to an array named e.g. tempNumbers
• For each item from n to the last, move it left by n
• Copy elements from tempNumbers to the end of the source array

Answer 4

Why don't you use a circular (double) linked list? In this case, you need to change your "start pointer".

Answer 5

Here is some kind of 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; } 

Answer 6

This will shift the array 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; 

Answer 7

 public static void shift(int[] arr, int offs) { // eg 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; }