Rotating an array by position n

Input is 1,2,3,4,5,6,7,8

If rotateOrder = 2

Output should be 7,8,1,2,3,4,5,6

If rotateOrder = 3

Output should be 6,7,8,1,2,3,4,5

Here is my program to do it:

int [] unOrderedArr = {1,2,3,4,5,6,7,8};
int  orderToRotate =2;

for(int i = 0; i<orderToRotate; i++){

for(int j = unOrderedArr.length-1; j>0; j--){
int temp = unOrderedArr[j];
unOrderedArr[j] = unOrderedArr[j-1];
unOrderedArr[j-1] = temp;

}

}

for(int j = 0; j<unOrderedArr.length; j++){
System.out.println("element is " + unOrderedArr[j]);

}

How can it be optimized?

• You can use the "Juggling Method" which is an in-place algorithm with complexity O(n). Nov 9 '14 at 15:10
• Using System.arraycopy is much faster than copying with a loop. However, the original question possibly expected you to implement it using a looping algorithm. Nov 9 '14 at 17:28

The current method doesn't check for invalid input:

• null array
• negative rotation order

if (arr == null || order < 0) {
throw new IllegalArgumentException("The array must be non-null and the order must be non-negative");
}

The posted code is messy. Use your IDE to reformat it to the standard:

int[] unOrderedArr = {1, 2, 3, 4, 5, 6, 7, 8};
int orderToRotate = 2;

for (int i = 0; i < orderToRotate; i++) {
for (int j = unOrderedArr.length - 1; j > 0; j--) {
int temp = unOrderedArr[j];
unOrderedArr[j] = unOrderedArr[j - 1];
unOrderedArr[j - 1] = temp;
}
}

Now that's a lot easier to read.

On a related note, an easy way to print an array is using Arrays.toString

Optimize

Frist of all, what will happen if you receive arr to rotate, and the rotate order = arr.length? The array elements will be rotated pointlessly, just to return to their original position. This gets even worse for multiples of arr.length.

Secondly, in this code:

for (int i = 0; i < order; i++) {
for (int j = arr.length - 1; j > 0; j--) {
// ...
}
}

The above code iterates over the entire array order times.

To avoid unnecessary iterations, you will benefit from using a clone of the original array, and iterate over the elements only once, at the expense of using twice as much memory.

Suggested implementation

The above suggestions and some style improvements applied:

private static void rotate(int[] arr, int order) {
if (arr == null || order < 0) {
throw new IllegalArgumentException("The array must be non-null and the order must be non-negative");
}
int offset = arr.length - order % arr.length;
if (offset > 0) {
int[] copy = arr.clone();
for (int i = 0; i < arr.length; ++i) {
int j = (i + offset) % arr.length;
arr[i] = copy[j];
}
}
}

Some unit test to verify it works:

@Test
public void testRotateBy2() {
int[] arr = {1, 2, 3, 4, 5, 6, 7, 8};
int[] expected = {7, 8, 1, 2, 3, 4, 5, 6};
rotate(arr, 2);
assertArrayEquals(expected, arr);
}

@Test
public void testRotateBy3() {
int[] arr = {1, 2, 3, 4, 5, 6, 7, 8};
int[] expected = {6, 7, 8, 1, 2, 3, 4, 5};
rotate(arr, 3);
assertArrayEquals(expected, arr);
}

@Test
public void testRotateByLength() {
int[] arr = {1, 2, 3, 4, 5, 6, 7, 8};
int[] expected = arr.clone();
rotate(arr, arr.length);
assertArrayEquals(expected, arr);
rotate(arr, arr.length * 3);
assertArrayEquals(expected, arr);
}

@Test
public void testRotateByZero() {
int[] arr = {1, 2, 3, 4, 5, 6, 7, 8};
int[] expected = arr.clone();
rotate(arr, 0);
assertArrayEquals(expected, arr);
}

There is a neat implementation ( following "Programming Pearls" ) that doesn't require temporary storage.

Assume that you have a method reverse(int[] array, int i, int, j) that reverses the portion of array between i and j (inclusive). Then rotate(int[] array, int rotateOrder) is implemented by (skipped boundary checks for berevity):

public rotate(int[] array, int k) {
int lastIndex = array.length-1;

reverse(array, 0, lastIndex);
reverse(array, 0, k-1);
reverse(array, k, lastIndex);
}

public void reverse(int[] a, int i , int j) {
int ii =  i;
int jj = j;

while (ii < jj) {
swap(ii, jj, a);
++ii;
--jj;
}
}

By having the call reverse(array, 0, lastIndex) be the last one, you get a rotation in the opposite direction

• Turns out that this is how Collections.rotate(List) is implemented (for non trivial sized input) Jul 3 '15 at 12:47

I would use different algorithm. Create new array and copy the data from the old one with an offset:

int[] rotate(final int[] unOrderedArr, final int orderToRotate) {
final int length = unOrderedArr.length;
final int[] rotated = new int[length];
for (int i = 0; i < length; i++) {
rotated[(i + orderToRotate) % length] = unOrderedArr[i];
}
return rotated;
}

It should be both simpler and faster - especially for big arrays and large offsets. The only downside is that you need to allocate additional array. For small offsets this might be the bottleneck. But, as always, you should benchmark first and identify which cases are worth optimizing.

As per the code in question there are three for loop to get the data. Here i am using only one for loop to get the element which we want to swap. Using java script in built functions to get the elements which we dont want to swap.

So steps are as follows:

1. Get array element which we don't want to swap store in temp array.
2. Check weather input element should not exceed the actual array length
3. Loop array element which we are swapping store in resultant array (result)
4. End Loop
5. Concat new array with slice array to get resultant output.
6. Print result

var numberArr = [1, 2, 3, 4, 5, 6];
var maxLength = numberArr.length;
var swapBy = 2;
var temp = numberArr.slice(0, (maxLength - swapBy));
var result = [];
if(swapBy > maxLength) {
}
for(var i = (maxLength - swapBy); i < maxLength; i++) {
result.push(numberArr[i]);
}
result.concat(temp);
//output will be
//[5, 6 ,1, 2, 3, 4]

I think this is optimize solution time as well as for space

Additional permutation of the solution. Includes optimization reducing the amount of cycles needed if they exceed the array length

private int[] getCyclicInts(int[] A, int K) {
if (A == null)
return A;

if (A.length <= 1)
return A;

if (K <= 0)
return A;

//make sure we don't do unneeded loops.
int actualIteration = K;
if (actualIteration >= A.length){
actualIteration = actualIteration % A.length;
}

if (actualIteration == 0)
return A;

int []  array = new int [A.length];

int index = 0;
for (int i=A.length - actualIteration  ; i < A.length; i++){
array[index] = A[i];
index ++;
}

for (int i=0 ; i < A.length - actualIteration; i++){
array[index] = A[i];
index ++;
}

return array;
}

Below is the $O(n)$ time complexity . I see it as optimized version of accepted solution as in accepted solution we are making copy of complete array but in below solution i am only copying the required elements instead of all. So better will be the memory space complexity though worst can be $O(n)$:

public static void main(String[] args) {
int[] unOrderedArr = { 1, 2, 3, 4, 5, 6, 7, 8 };
int rotationOrder = 3;

/**
* this will store the last n elements which need to be shifted in
* beginning
**/

if (unOrderedArr.length != rotationOrder) {

int[] temp = new int[rotationOrder];
int tempPointer = unOrderedArr.length - rotationOrder;

for (int i = 0; i < temp.length; ++i) {
temp[i] = unOrderedArr[tempPointer++];

}

for (int i = unOrderedArr.length - rotationOrder - 1; i >= 0; --i) {

unOrderedArr[i + rotationOrder] = unOrderedArr[i];
}

for (int i = 0; i < temp.length; ++i) {
unOrderedArr[i] = temp[i];

}
}

// print the output
for (int i = 0; i < unOrderedArr.length; ++i) {
System.out.println(unOrderedArr[i]);

}

}