What algorithm is more efficient to shift every elements in a java array?

Question

this is the first algorithm that i made:

int tmp = null;
for (int i = arr.length-1; i > 0; i--){
    tmp = arr[i];
    arr[i] = arr[i-1];
    arr[i-1] = tmp;
}

and this is the second algorithm which my computer teacher says to me:

int tmp = null;
for (int i = arr.length-1; i > 0; i--){
    for(int j = 0; j < arr.length; j++){
    tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
    }
}

help me about which is more efficient. In my experiment using

System.currentTimeMillis();

this method with an array with 100000 datas, the first algorithm was faster but my teacher says the second one would be faster in bigger databases with various things. I know that a LinkedList would do good, but i want to know about this problem.

I'm not clear exactly what you're trying to do - but the second one is clearly O(n^2), whereas the first is O(n), i.e. the second one gets slower quicker for bigger inputs. — Andy Turner
– Andy Turner, Commented Sep 8, 2016 at 12:54
I won't answer your question directly, but I believe it's better to remember number of shifts and write your own get method which would handle number of shifts. — xenteros
– xenteros, Commented Sep 8, 2016 at 12:54
Yes, I'm surprised that your teacher is claiming that the second algorithm is faster. — fmt
– fmt, Commented Sep 8, 2016 at 12:54
But the first one can be made faster again, by avoiding two of the assignments: int tmp = arr[arr.length - 1]; for (int i = arr.length - 1; i > 0; --i) { arr[i] = arr[i - 1]; } arr[0] = tmp; or something like that. — Andy Turner
– Andy Turner, Commented Sep 8, 2016 at 12:56

Andy Turner · Accepted Answer · 2016-09-08 13:04:40Z

4

The algorithms do different things:

Input: [1, 2, 3, 4, 5]
First: [5, 1, 2, 3, 4]
Second: [3, 4, 1, 2, 5]

so any discussion of their relative efficiency is irrelevant, as they are not functionally the same.

However, simply in terms of the time taken to do something, the first algorithm is O(n), whereas the second is O(n^2). As such, the time taken to execute the first will grow more slowly than the second as the input size grows, so your teacher is wrong.

Note that the first is doing a lot of unnecessary work: it is repeatedly swapping the last element of the array all the way down to the start of the array. As such, it can be done more quickly like this:

int tmp = arr[arr.length - 1];
for (int i = arr.length - 1; i > 0; --i) {
  arr[i] = arr[i - 1];
}
arr[0] = tmp;

answered Sep 8, 2016 at 13:04

Andy Turner

141k11 gold badges169 silver badges263 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

What algorithm is more efficient to shift every elements in a java array?

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related