Sort a nxn matrix (2D Array)

Question

During a programming test I was asked to write a Java program to perform sorting on a 3x3 matrix. i.e. I was given a matrix (a 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 an output matrix

1 2 3  
4 5 6 
7 8 9 

What I did was to convert this 3x3 matrix into a 1D array

a[9] = {2,6,1,3,5,7,4,8,9}

and performed bubble sort on this array and converted the resultant array back to a 2D array.

I was not satisfied with this approach as I felt this approach is very cheesy. Is there a better way to do this.

Edit: I would like to remove the array conversion part. Any sorting algorithm can be used and would like to perform sort on the matrix (2D array) itself.

Answer 1

Well under your strange requirements you can create a view list backed by the input matrix and sort it using the standard 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 just define our own get and set methods which 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]]

Answer 2

For less time complexity you could use an other sorting algorithm, like quicksort or maybe radixsort (because you only deal with numbers).

Converting the matrix into an array isn't your major time consumption method, but the sorting is. So optimizing that and only afterwards try different methods.

edit:

According to your data layout m[3][3], you could use bucket sort (this could lead to a greater performance gain, if you use m[1000][1000]. Because you already have buckets which you can sort, this will remove the necessity to convert it first.