Algorithm to Sort the Columns of a Matrix using Transpose

Given a two-dimensional integer matrix, sort each of the columns in ascending order.

Example 1
Input

1 2 3 4 5

matrix = [     [10, 20, 30],     [5, 5, 3],     [0, 10, 7] ]

matrix = [
    [10, 20, 30],
    [5, 5, 3],
    [0, 10, 7]
]

Output

1 2 3 4 5

[     [0, 5, 3],     [5, 10, 7],     [10, 20, 30] ]

[
    [0, 5, 3],
    [5, 10, 7],
    [10, 20, 30]
]

Column Sort

In order to utilize the inbuilt/provided sorting library, we have to transpose the matrix so that the columns are continuous arrays. Then after sorting, we need to transpose the matrix back.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

vector<vector<int>> solve(vector<vector<int>>& matrix) {
    function<void(vector<vector<int>> &m)> transpose = [](vector<vector<int>> &m) {
        vector<vector<int>> n(m[0].size(), vector<int>(m.size()));
        for (int r = 0; r < m.size(); ++ r) {
            for (int c = 0; c < m[0].size(); ++ c) {
                n[c][r] = m[r][c];
            }
        }
        m = n;
    };
    transpose(matrix);
    for (int r = 0; r < matrix.size(); ++ r) {
        sort(begin(matrix[r]), end(matrix[r]));
    }
    transpose(matrix);
    return matrix;
}

vector<vector<int>> solve(vector<vector<int>>& matrix) {
    function<void(vector<vector<int>> &m)> transpose = [](vector<vector<int>> &m) {
        vector<vector<int>> n(m[0].size(), vector<int>(m.size()));
        for (int r = 0; r < m.size(); ++ r) {
            for (int c = 0; c < m[0].size(); ++ c) {
                n[c][r] = m[r][c];
            }
        }
        m = n;
    };
    transpose(matrix);
    for (int r = 0; r < matrix.size(); ++ r) {
        sort(begin(matrix[r]), end(matrix[r]));
    }
    transpose(matrix);
    return matrix;
}

Transposing the matrix takes O(NM) time and space. Then sorting takes O(MNLogN) where N is the number of rows and M is the number of columns.

–EOF (The Ultimate Computing & Technology Blog) —