Program to rotate an array

Question

I wrote this code where I have to rotate an array of 'n' elements by 'd' elements in the anti-clockwise direction.Can it be done in a better and simpler way?

 public class RotateArr{
     public static void rotate(int[] arr,int d,int n){


    System.out.println("Array before rotating : ");

    for(int l=0; l<n; l++){
        System.out.print(arr[l]+" ");
    }
        System.out.println();

    int temp = arr[0];

    for(int i=0; i<d; i++){
        for(int j=1; j<n; j++){
            arr[j-1] = arr[j];
            if(j==(n-1)){
                arr[n-1] = temp;
            }
        }
        temp = arr[0];
    }

    System.out.println("Array after rotating");
    for(int k=0; k<n; k++){
        System.out.print(arr[k]+" ");
    }
}
    public static void main(String[] args) {

    int[] arr = {1,2,3,4,5,6,7};

    int d = 3;

    int n = arr.length;

    rotate(arr,d,n);
      }
   }

Answer 1

Suggestions

I guess you are coming from a C/C++ background. Java arrays have a property called length, which gives its size, so you don't need the parameter n. Just use arr.length wherever you have used n.

I actually once thought that swapping the first element with every other element d times was an original algorithm for rotating an array I had thought up myself, and it's in-place but this has a time complexity of O(n*d). There exists a better algorithm working in O(n) time, which uses the idea: Instead of moving one by one, divide the array into different sets where the number of sets is equal to the GCD of n and d and move the elements within the sets.

In Java, the code would look like this (note: This only does a left rotation):

void rotate(int[] arr, int d) {
    int i, j, k, temp;
    for (i = 0; i < gcd(d, arr.length); i++) {
        /* move i-th values of blocks */
        temp = arr[i];
        j = i;
        while (1 != 0) 
        {
            k = j + d;
            if (k >= arr.length) 
                k = k - arr.length;
            if (k == i) 
                break;
            arr[j] = arr[k];
            j = k;
        }
        arr[j] = temp;
    }
}

/*Function to get gcd of a and b*/
int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    else {
        return gcd(b, a % b);
    }
}

This version of rotate(int[], int) rotates the passed array in-place, so you can just print out the elements in a loop later. For printing, hoping you are on JDK 5 or greater, use the for-each loop:

for(int element : arr) {
    System.out.println(element);
}

And why restrict yourself to arrays of ints? With generics, you could have the following modifications and make this rotation routine work with all types of arrays of objects (note that int is not an object, it is a primitive type, you'll need to use Integer, which is the object-oriented wrapper type for int, instead of int. Same goes for double and other primitive types, you'll need to use arrays of their wrapper types, look this up).

<T> void rotate(T[] arr, int d) {
    int i, j, k;
    T temp;
    ...

Style

You have inconsistent indentation and spacing. If you are using some very simple text editor like Notepad for writing your programs, you might one check out editors with auto-formatting of code, or use an IDE. Also, you don't have proper whitespace surrounding binary operators. Finally, your variable names are somewhat nondescriptive, but in this case it would have been OK if you had properly documented your methods.

Answer 2

1. Separation of concerns. Ideally, one method should do one thing. I would expect the rotate method to actually rotate the array. That's it. Your method also prints something to the standard output. There are two reasons why it's bad. Firstly, it's confusing. Secondly, it introduces more reasons for the method to change. For instance, if you need to change the format of the output or write it to the file, you have to change the rotate method. It's not convenient, is it?

2. The interface is quite strange. The n parameter of the rotate method is redundant (it's expected to be equal to the length of the array, isn't it?). It also makes the interface less clear (what if I pass a different value of n?).

3. The algorithm itself is not efficient. Shifting the array be one d times requires O(n * d) time. There are at least two ways to make it linear. The first one is pretty simple. You can copy the entire array to a buffer and that assign res[i] = buffer[(i + d) % buffer.length] in a loop. However, it requires additional memory. The second one uses a constant amount of space and O(n) operations. It goes like this: to cyclically shift an array by k positions to the left, one can reverse the [0, k - 1] range, then reverse the [k, n - 1] range and finally reverse the entire array.

4. Documenting your code is a good practice. It's not clear what the valid range of values for d is from your code itself. It's also not clear whether it performs a left or a right shift.

5. Your code formatting violates the Java coding conventions. The indentation is kind of messed up. The binary operators are not surrounded with whitespaces. The names of the variables are not meaningful (for example, what does d stand for?). That's why it's hard to read.

Answer 3

It would be better to organize your program to multiple methods, each having a single responsibility. It would reveal the overall logic better, improving readability, and you would end up with reusable elements and less code duplication. Consider this:

static void rotate(int[] arr, int k) {
    // just rotate the array, do nothing else
}

static void printArray(int[] arr) {
    // just print the array, do nothing else
}

static void rotateAndPrint(int[] arr, int k) {
    printArray(arr);
    rotate(arr, k);
    printArray(arr);
}

The JDK provides a very easy way to print an array:

System.out.println(Arrays.toString(arr));

Your algorithm works by rotating the entire content of the array k times. By using extra space, you can rotate much faster:

k = k % arr.length;
int[] rotated = Arrays.copyOf(arr, k);
System.arraycopy(arr, k, arr, 0, arr.length - k);
System.arraycopy(rotated, 0, arr, arr.length - k, k);

Last but not least, the formatting of your code is quite poor. I suggest to copy-paste into one of the well-known IDEs such as IntelliJ or Eclipse and use the auto-format feature.

Answer 4

Get the length from the array itself

Getting the length of an array is O(1) (very fast regardless of the array length) so you can avoid asking the array length as the argument of the function because it is an unnecessary burden on the user.