Arrays - Building Java Programs: A Back to Basics Approach - page 456

[0] [1] [2] [3] [4] [5]

list 78 8 7 -2 14 3

i j

list 78 14 7 -2 8 3

i j

list 78 14 -2 7 8 3

ij

list 78 14 7 -2 8 3

ji

list 78 8 7 -2 14 3

j i

list 3 8 7 -2 14 78

j i

The values of i and j cross halfway through this process. As a result, the first
three swaps successfully reverse the array, and then the three swaps that follow undo
the work of the first three. To fix this problem, you need to stop it halfway through
the process. This task is easily accomplished by changing the test:

for (int i = 0; i < list.length / 2; i++) {
int j = list.length - i - 1;
swap(list, i, j);

}

In the sample array, list.length is 6 . Half of that is 3 , which means that this
loop will execute exactly three times. That is just what you want in this case (the first
three swaps), but you should be careful to consider other possibilities. For example,
what if list.length were 7 ? Half of that is also 3 , because of truncating division. Is
three the correct number of swaps for an odd-length list? The answer is yes. If there
are an odd number of elements, the value in the middle of the list does not need to be
swapped. So, in this case, a simple division by 2 turns out to be the right approach.
Including this code in a method, you end up with the following overall solution:

public static void reverse(int[] list) {
for (int i = 0; i < list.length / 2; i++) {
int j = list.length - i - 1;
swap(list, i, j);

}

}