Sort nxn matrix (2D array)
During a programming test, I was asked to write a Java program to sort by a 3x3 matrix. that is, I was given a matrix (2D array, say m[3][3]
)
2 6 1
3 5 7
4 8 9
I was asked to sort this matrix which should give the output matrix
1 2 3
4 5 6
7 8 9
I did to convert this 3x3 matrix to 1D array
a[9] = {2,6,1,3,5,7,4,8,9}
and performed bubble sort on that array and converted the resulting array back to 2D array.
I was not happy with this approach as I felt that this approach was very crappy. Is there a better way to do this.
Edit . I would like to remove the transformation part of the array. Any sorting algorithm can be used and would like to sort by the matrix itself (2D array).
source to share
Well for your weird requirements you can create a list of views supported by the input matrix and sort it using the standard one Collections.sort
:
public static void sortMatrix(final int[][] matrix) {
// Assuming the matrix is rectangular
final int n = matrix.length;
final int m = matrix[0].length;
List<Integer> list = new AbstractList<Integer>() {
@Override
public Integer set(int index, Integer element) {
return matrix[index/m][index%m] = element;
}
@Override
public Integer get(int index) {
return matrix[index/m][index%m];
}
@Override
public int size() {
return n*m;
}
};
Collections.sort(list);
}
Here we simply define our own methods get
and set
that change the corresponding matrix element. Usage example:
int[][] matrix = {{2,6,1},{3,5,7},{4,8,9}};
sortMatrix(matrix);
System.out.println(Arrays.deepToString(matrix));
Output:
[[1, 2, 3], [4, 5, 6], [7, 8, 9]]
source to share
For less time complexity, you can use a different sorting algorithm such as quicksort or perhaps radixsort (because you only deal with numbers).
Converting a matrix to an array is not your main time consuming method, but sorting. So optimize it and only then try different methods.
change
According to your data layout, m[3][3]
you can use cart sorting (this can lead to performance gain if you are using m[1000][1000]
. Since you already have buckets that you can sort, this will eliminate the need to convert it in the first place.
source to share
public int[][] sortMatrix(int matrix[][], int r, int c) {
for (int k = 0; k < r * c; k++) {
Integer current = null;
Integer previous = null;
Integer currentI = null;
Integer currentJ = null;
Integer previousI = null;
Integer previousJ = null;
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
current = matrix[i][j];
currentI = i;
currentJ = j;
if (previous != null) {
if (current < previous) {
matrix[currentI][currentJ] = previous;
matrix[previousI][previousJ] = current;
}
}
previous = matrix[i][j];
previousI = i;
previousJ = j;
}
}
}
return matrix;
}
source to share
You have N integers, converting them from 2D -> 1D array and 1D -> 2D array cannot take longer O (N) time when sorting in general takes longer than what means Sort dominates your temporal complexity. However, you should focus on implementing more efficient sorting.
Try using heap sort, for example, which time complexity is O (NlogN), which is faster than bubble sort (O (N ^ 2)). As your input increases, you will see a significant difference in the amount of time your process takes.
source to share
You can use Streams
:
public int[][] sortWithStreams(int[][] matrix) {
return Arrays.stream(matrix)
// Turn it into a stream of ints by streaming each row.
.flatMapToInt(x -> Arrays.stream(x))
// Sort it.
.sorted()
// Gather the now sorted stream back into a new array.
.collect(
// A new matrix.
() -> new int[matrix.length][matrix[0].length],
// Consumer folds each value into the next position in an array.
new ObjIntConsumer<int[][]>() {
// Start at [0][0]
int x = 0, y = 0;
@Override
public void accept(int[][] t, int value) {
// Place it and step on.
t[y][x++] = value;
// Wrap if necessary.
if (x >= t[y].length) {
x = 0;
y += 1;
}
}
},
// As `sorted` cannot generate a parallel stream it is safe to ignore the combiner.
null);
}
public void test() {
int[][] matrix1 = {{2, 6, 1}, {3, 5, 7}, {4, 8, 9}};
int[][] matrix2 = {{2, 6, 1, 12}, {3, 5, 7, 10}, {4, 8, 9, 11}};
int[][] matrix3 = {{2, 6, 1}, {3, 5, 7}, {4, 8, 9}, {1, 3, 12}};
// Print them.
System.out.println(Arrays.deepToString(sortWithStreams(matrix1)));
System.out.println(Arrays.deepToString(sortWithStreams(matrix2)));
System.out.println(Arrays.deepToString(sortWithStreams(matrix3)));//
}
source to share