How to improve efficiency of the Algorithm?

Question

I have to swap numbers in an array 'd' times, so that left rotation of the array can be done. 'd' is the number of rotations of the array. Suppose if the array is 1->2->3->4->5 and if the d=1 then after one left rotation the array will be 2->3->4->5->1.

I have used the following code for performing the above operation:

for (int rotation = 0; rotation < d; rotation++) {
    for (int i = 1; i < a.length; i++) {

        int bucket = a[i - 1];
        a[i - 1] = a[i];
        a[i] = bucket;

    }
}

But the efficiency of this algorithm is too high, probably O(n^d) worst case. How to improve the efficiency of the algorithm, especially in the worst case?

I am looking for a RECURSIVE approach for this algorithm. I came up with:

    public static void swapIt(int[] array, int rotations){


        for(int i=1; i<array.length; i++){
            int bucket = array[i-1];
            array[i-1] = array[i];
            array[i] = bucket;  
        }

          rotations--;  

        if(rotations>0){
            swapIt(array,rotations); 
        }

        else{

            for(int i=0; i<array.length; i++){
            System.out.print(array[i]+" "); 

            }

        }

    }

This RECURSIVE algorithm worked, but again efficiency is the issue. Can not use it for larger arrays.

Answer 1

Komplexity of your algorithm looks like O(n*d) to me.

My approach would be not to rotate by one d times, but to rotate by d one time.

You can calculate the destination of an element by:

So instead of a[i - 1] = a[i]; You would do this:

a[(i + a.length - d) % a.length] = a[i];

the Term (i + a.length - d) % a.length handles that you always get values in the intervall: 0... a.length-1

Explanation:

i + a.length - d is always positive (as long as d is <= a.length) but it could be greater/equal than a.length what would not be allowed. So take the reminder of the division with a.length.

This way you get for every i= 0.. a.length-1 the right new position.

---

As mentioned by Satyarth Agrahari: If d>n you need to reduce d. d= d % a.length to ensure that (i + a.length - d) % a.length is in the wanted interval 0... a.length-1. The result is the same because rotation by a.length is like doing nothing at all.