Reversing arrays is part of a collection of standard algorithms.
Reversing the order of the elements in an array can be accomplished in-place or by constructing a new array. The algorithms are very similar.
The same algorithms can be applied to a 2D array. When reversing the elements in a 2D array, the desired final ordering must be clear (as there are several interpretations).
Reversing a 1D array in-place
Algorithm
Loop through the first half.
Calculate the index of the corresponding value in the second half.
Swap the values.
Implementation in Java
public static void reverseInPlace(int[] vals)
{
for(int i = 0; i < vals.length / 2; i++)
{
int j = vals.length - 1 - i;
int temp = vals[i];
vals[i] = vals[j];
vals[j] = temp;
}
}
The expression vals.length - 1 is the index of the last element in vals.
The expression vals.length - 1 - i is the index i positions from the right end of the array (and is sometimes written as vals.length - i - 1).
Return a 1D array in reverse order
Algorithm
Create a new array with the same length as the original array.
Loop through the entire original array.
Calculate the index at which the value from the original array is to be placed in the new array.
Copy the value from the original array to the new array.
Return the new array.
Implementation in Java
public static int[] getReversed(int[] vals)
{
int[] reversed = new int[vals.length];
for(int i = 0; i < vals.length; i++)
{
int j = vals.length - 1 - i;
reversed[j] = vals[i];
}
return reversed;
}
The expression vals.length - 1 - i serves the same purpose as in the in-place version. It is the index at which the element originally at i should be placed in the new array.
Reversing a 2D array
This demonstration assumes familiarity with 2D arrays, including treating a 2D array as an array of 1D arrays.
Interpretation
For this demonstration, reversing a 2D array is interpreted as reversing the order of the rows and reversing the order of the elements within each row.
Original 2D array:
[[1, 2, 3],
[4, 5, 6],
[7, 8, 9],
[10, 11, 12]]
Desired result:
[[12, 11, 10],
[9, 8, 7],
[6, 5, 4],
[3, 2, 1]]
Algorithm
Loop through the first half of the rows.
Calculate the index of the corresponding value in the second half.
Swap the values (row references).
Call reverseInPlace with both the original row and the swapped row.
This algorithm treats the 2D array as an array of 1D arrays. The algorithm uses reverseInPlace to reverse the elements within each row (each 1D array).
As an alternative, it is possible to reverse the elements within each row directly, using the same algorithm as in reverseInPlace.
Implementation in Java
public static void reverse2D(int[][] matrix)
{
for(int origRow = 0; origRow < matrix.length / 2; origRow++)
{
int newRow = matrix.length - 1 - origRow;
int[] temp = matrix[origRow];
matrix[origRow] = matrix[newRow];
matrix[newRow] = temp;
reverseInPlace(matrix[origRow]);
reverseInPlace(matrix[newRow]);
}
}
Help & comments
Get help from AP CS Tutor Brandon Horn