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 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;
}
}
PHP
<?php // PHP implementation to sort // the matrix row-wise and // column-wise $MAX_SIZE = 10; // function to sort each // row of the matrix function sortByRow(&$mat, $n) { for ($i = 0; $i < $n; $i++) // sorting row number 'i' sort($mat[$i]); } // function to find // transpose of the matrix function transpose(&$mat, $n) { for ($i = 0; $i < $n; $i++) { for ($j = $i + 1; $j < $n; $j++) { // swapping element at index (i, j) // by element at index (j, i) $t = $mat[$i][$j]; $mat[$i][$j] = $mat[$j][$i]; $mat[$j][$i] = $t; } } } // function to sort // the matrix row-wise // and column-wise function sortMatRowAndColWise(&$mat, $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 function printMat(&$mat, $n) { for ($i = 0; $i < $n; $i++) { for ($j = 0; $j < $n; $j++) echo $mat[$i][$j] . " "; echo " "; } } // Driver Code $mat = array(array( 4, 1, 3 ), array( 9, 6, 8 ), array( 5, 2, 7 )); $n = 3; echo "Original Matrix: "; printMat($mat, $n); sortMatRowAndColWise($mat, $n); echo " Matrix After Sorting: "; printMat($mat, $n); // This code is contributed // by ChitraNayal ?> |
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!
Share your thoughts in the comments
