Given a n x n matrix. The problem is to sort the matrix row-wise and column wise.
Examples:
Input : mat[][] = { {4, 1, 3},
{9, 6, 8},
{5, 2, 7} }
Output : 1 3 4
2 5 7
6 8 9
Input : mat[][] = { {12, 7, 1, 8},
{20, 9, 11, 2},
{15, 4, 5, 13},
{3, 18, 10, 6} }
Output : 1 5 8 12
2 6 10 15
3 7 11 18
4 9 13 20
Approach: Following are the steps:
- Sort each row of the matrix.
- Get transpose of the matrix.
- Again sort each row of the matrix.
- Again get transpose of the matrix.
Algorithm for sorting each row of matrix using C++ STL sort():
for (int i = 0 ; i < n; i++)
sort(mat[i], mat[i] + n);
Algorithm for getting transpose of the matrix:
for (int i = 0; i < n; i++) {
for (int j = i + 1; i < n; i++) {
int temp = mat[i][j];
mat[i][j] = mat[j][i];
mat[j][i] = temp;
}
}
C++
// C++ implementation to sort the matrix row-wise // and column-wise #include <bits/stdc++.h> using namespace std; #define MAX_SIZE 10 // function to sort each row of the matrix void sortByRow(int mat[MAX_SIZE][MAX_SIZE], int n) { for (int i = 0; i < n; i++) // sorting row number 'i' sort(mat[i], mat[i] + n); } // function to find transpose of the matrix void transpose(int mat[MAX_SIZE][MAX_SIZE], int n) { for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++) // swapping element at index (i, j) // by element at index (j, i) swap(mat[i][j], mat[j][i]); } // function to sort the matrix row-wise // and column-wise void sortMatRowAndColWise(int mat[MAX_SIZE][MAX_SIZE], int n) { // sort rows of mat[][] sortByRow(mat, n); // get transpose of mat[][] transpose(mat, n); // again sort rows of mat[][] sortByRow(mat, n); // again get transpose of mat[][] transpose(mat, n); } // function to print the matrix void printMat(int mat[MAX_SIZE][MAX_SIZE], int n) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) cout << mat[i][j] << " "; cout << endl; } } // Driver program to test above int main() { int mat[MAX_SIZE][MAX_SIZE] = { { 4, 1, 3 }, { 9, 6, 8 }, { 5, 2, 7 } }; int n = 3; cout << "Original Matrix: "; printMat(mat, n); sortMatRowAndColWise(mat, n); cout << " Matrix After Sorting: "; printMat(mat, n); return 0; } |
Output:
Original Matrix: 4 1 3 9 6 8 5 2 7 Matrix After Sorting: 1 3 4 2 5 7 6 8 9
Time Complexity: O(n2log2n).
Auxiliary Space: O(1).
Please refer complete article on Sort the matrix row-wise and column-wise for more details!
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
