1

A array a is given with n elements, and we need to swap the elements d number of times. The below code works fine for smaller n and d values, but when the n and d values are in the order of 10^5. The time consumed is huge. How do I optimize the code?

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

    }

And could you recommend good sources to learn about time complexity and code optimization?

Improve this question
9
  • You do the same thing d times. Removing the outer loop would make it d times faster. Commented Jun 6, 2020 at 12:16
  • use List instead of Array. with list you can remove object on one position, and add it on other Commented Jun 6, 2020 at 12:18
  • @AndyTurner I know that, how do I do that without for or while loop is the question? Commented Jun 6, 2020 at 12:19
  • @anatoli But the problem needs to be done usingarrays. Not using lists. Commented Jun 6, 2020 at 12:20
  • One optimizaton that is definitely required is to declare the varaible's j ,temp outside of loop Commented Jun 6, 2020 at 12:35

4 Answers 4

Reset to default
2

What you're doing here is left-shifting the array by d places without using allocating additional storage.

To do a left-shift by d places:

  • Reverse the whole array (n/2 swaps)
  • Reverse the first n-d elements in the array ((n-d)/2 swaps)
  • Reverse the last d elements in the array (d/2 swaps)

This does n swaps in total (and independent of d), so its time complexity is O(n).

You can implement this like so:

void reverse(int[] arr, int from, int to) {
  while (from+1 < to) {
    --to;
    int tmp = arr[from];
    arr[from] = arr[to];
    arr[to] = tmp;
    ++from;
  }
}

int n = arr.length;
reverse(arr, 0, n);
reverse(arr, 0, n-d);
reverse(arr, n-d, n);
Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

1

If you think about it, you need to swap d times all elements of an array which has the lenght of n elements. This makes an O(n*d) which is O(n^2) with d = n. If you realy need to swap each element, there is no improvement in my point of view.

But if you only want the result, this code is much better:

public static int[] change(int[] array, int d) {
    int[] tempArray = new int[array.length];
    for (int i = 0; i < array.length; ++i) {
        int place = Math.floorMod(i - d, array.length);       //calculating the new index for array[i]
        tempArray[place] = array[i];
    }
    return tempArray;
}

This code has an O(n). If you know about modulo calculation, you should understand what I am doing.

Improve this answer

4 Comments

It's worth pointing out that it would be simpler (albeit more opaque) to replace the loop with two calls to System.arraycopy: System.arraycopy(array, d, tempArray, 0, n-d); System.arraycopy(array, n-d, tempArray, n-d, d);, or something like that.
Thanks @AndyTurner I didn't know this because I just started learning Java. But it is very interresing.
@AndyTurner but wouldn't the second invokation need to be System.arraycopy(array, 0, tempArray, n-d, d);? First you copyed all elements starting from d to the end of the original array. Now we need to copy the array from index 0 to index d or am I wrong?
you could well be right. I said "something like" ;)
1

If what is intended in your algorithm is to shift element d times, then you don't really need 2 loops: you need one and only one loop.

I tested your with an array of size 100000000, and it took 5463 seconds.

My solution, however, took 1702 ms.

Swapping actually is not necessary. Instead, using Insertion sort "technique" is better.

The proposed solution to contemplate is as the following:

void rotate(int d) {
    for (int i = 0; i < d; i++) {
        rightShift();
    }
}

void rightShift() {
    int v = a[a.length - 1];
    for (int i = a.length - 2; i >= 0 ; i --) {
        a[i + 1] = a[i];
    }
    a[0] = v;
}

Please note that you don't need to perform unnecessary swaps (when d >= n).

To solve this problem, use d = d % n.

Improve this answer

2 Comments

If you think about it, you are still using two loops. In rotate() is one for-loop in which you are calling rightShift() with another for-loop. Because of this, the time complexity is still O(n*d).
Indeed, but d is signifcantly smaller than n.
0 
Integer[] temp = new Integer[d];

// store moved items in temp
for (int i = 0; i < d; i++) {
    temp[i] = a[i];
}

// replace once items in array
for (int j = 0; i < n - 1; i++) {
    a[j] = a[j+d];
}

// add on end the temp items
for (int i = 0; i < d; i++) {
    a[n + i] = temp[i];
}

this reduce complexity by d calls

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.