Sort the matrix column-wise
Given a matrix mat[][] of dimensions N * M, the task is to sort each column of a matrix in ascending order and print the updated matrix.
Examples:
Input: mat[][] = { {1, 6, 10}, {8, 5, 9}, {9, 4, 15}, {7, 3, 60} }
Output:
1 3 9
7 4 10
8 5 15
9 6 60
Explanation:
The input matrix is sorted in a column wise manner,
1 < 7 < 8 < 9
3 < 4 < 5 < 6
9 < 10 < 15 < 60Input: arr[][] = { {1, 6}, {8, 4}, {9, 7} }
Output:
1 4
8 6
9 7
Approach: Follow the steps below to solve the problem:
- Traverse the matrix
- Find the transpose of the given matrix mat[][].
- Store this transpose of mat[][] in a 2D vector, tr[][]
- Traverse the rows of the matrix tr[][]
- Sort each row of the matrix using the sort function.
- Store the transpose of tr[][] in mat[][]
- Print the matrix, mat[][]
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the transpose // of the matrix mat[] vector<vector< int > > transpose( vector<vector< int > > mat, int row, int col) { // Stores the transpose // of matrix mat[][] vector<vector< int > > tr( col, vector< int >(row)); // Traverse each row of the matrix for ( int i = 0; i < row; i++) { // Traverse each column of the matrix for ( int j = 0; j < col; j++) { // Transpose matrix elements tr[j][i] = mat[i][j]; } } return tr; } // Function to sort the given // matrix in row wise manner void RowWiseSort(vector<vector< int > >& B) { // Traverse the row for ( int i = 0; i < ( int )B.size(); i++) { // Row - Wise Sorting sort(B[i].begin(), B[i].end()); } } // Function to print the matrix // in column wise sorted manner void sortCol(vector<vector< int > > mat, int N, int M) { // Function call to find transpose // of the matrix mat[][] vector<vector< int > > B = transpose(mat, N, M); // Sorting the matrix row-wise RowWiseSort(B); // Calculate transpose of B[][] mat = transpose(B, M, N); // Print the matrix mat[][] for ( int i = 0; i < N; i++) { for ( int j = 0; j < M; j++) { cout << mat[i][j] << " " ; } cout << '\n' ; } } // Driver Code int main() { // Input vector<vector< int > > mat = { { 1, 6, 10 }, { 8, 5, 9 }, { 9, 4, 15 }, { 7, 3, 60 } }; int N = mat.size(); int M = mat[0].size(); // Function call to print the matrix // in column wise sorted manner sortCol(mat, N, M); return 0; } |
Java
// Java program for the above approach import java.util.*; import java.util.Arrays; class GFG{ // Function to find the transpose // of the matrix mat[] static int [][] transpose( int [][] mat, int row, int col) { // Stores the transpose // of matrix mat[][] int [][] tr = new int [col][row]; // Traverse each row of the matrix for ( int i = 0 ; i < row; i++) { // Traverse each column of the matrix for ( int j = 0 ; j < col; j++) { // Transpose matrix elements tr[j][i] = mat[i][j]; } } return tr; } // Function to sort the given // matrix in row wise manner static void RowWiseSort( int [][] B) { // Traverse the row for ( int i = 0 ; i < ( int )B.length; i++) { // Row - Wise Sorting Arrays.sort(B[i]); } } // Function to print the matrix // in column wise sorted manner static void sortCol( int [][] mat, int N, int M) { // Function call to find transpose // of the matrix mat[][] int [][] B = transpose(mat, N, M); // Sorting the matrix row-wise RowWiseSort(B); // Calculate transpose of B[][] mat = transpose(B, M, N); // Print the matrix mat[][] for ( int i = 0 ; i < N; i++) { for ( int j = 0 ; j < M; j++) { System.out.print(mat[i][j] + " " ); } System.out.println(); } } // Driver Code public static void main(String[] args) { // Input int [][] mat = { { 1 , 6 , 10 }, { 8 , 5 , 9 }, { 9 , 4 , 15 }, { 7 , 3 , 60 } }; int N = mat.length; int M = mat[ 0 ].length; // Function call to print the matrix // in column wise sorted manner sortCol(mat, N, M); } } // This code is contributed by ukasp |
Python3
# Python3 program for the above approach # Function to find the transpose # of the matrix mat[] def transpose(mat, row, col): # Stores the transpose # of matrix mat[][] tr = [[ 0 for i in range (row)] for i in range (col)] # Traverse each row of the matrix for i in range (row): # Traverse each column of the matrix for j in range (col): # Transpose matrix elements tr[j][i] = mat[i][j] return tr # Function to sort the given # matrix in row wise manner def RowWiseSort(B): # Traverse the row for i in range ( len (B)): # Row - Wise Sorting B[i] = sorted (B[i]) return B # Function to print the matrix # in column wise sorted manner def sortCol(mat, N, M): # Function call to find transpose # of the matrix mat[][] B = transpose(mat, N, M) # Sorting the matrix row-wise B = RowWiseSort(B) # Calculate transpose of B[][] mat = transpose(B, M, N) # Print the matrix mat[][] for i in range (N): for j in range (M): print (mat[i][j], end = " " ) print () # Driver Code if __name__ = = '__main__' : # Input mat = [ [ 1 , 6 , 10 ], [ 8 , 5 , 9 ], [ 9 , 4 , 15 ], [ 7 , 3 , 60 ] ] N = len (mat) M = len (mat[ 0 ]) # Function call to print the matrix # in column wise sorted manner sortCol(mat, N, M) # This code is contributed by mohit kumar 29. |
C#
// C# program for the above approach using System; using System.Linq; class GFG { // Function to find the transpose // of the matrix mat[] static int [,] Transpose( int [,] mat, int row, int col) { // Stores the transpose of matrix mat[][] int [,] tr = new int [col, row]; // Traverse each row of the matrix for ( int i = 0; i < row; i++) { // Traverse each column of the matrix for ( int j = 0; j < col; j++) { // Transpose matrix elements tr[j, i] = mat[i, j]; } } return tr; } // Function to sort the given matrix // in row wise manner static void RowWiseSort( int [,] B, int row, int col) { // Traverse the row for ( int i = 0; i < row; i++) { // Convert the 2D matrix to 1D array int [] rowElements = Enumerable.Range(0, col).Select(x => B[i, x]).ToArray(); // Row-wise sorting Array.Sort(rowElements); // Convert the sorted 1D array back to 2D matrix for ( int j = 0; j < col; j++) { B[i, j] = rowElements[j]; } } } // Function to print the matrix // in column wise sorted manner static void SortCol( int [,] mat, int N, int M) { // Function call to find transpose // of the matrix mat[][] int [,] B = Transpose(mat, N, M); // Sorting the matrix row-wise RowWiseSort(B, M, N); // Calculate transpose of B[][] mat = Transpose(B, M, N); // Print the matrix mat[][] for ( int i = 0; i < N; i++) { for ( int j = 0; j < M; j++) { Console.Write(mat[i, j] + " " ); } Console.Write( "\n" ); } } // Driver Code public static void Main( string [] args) { // Input int [, ] mat = { { 1, 6, 10 }, { 8, 5, 9 }, { 9, 4, 15 }, { 7, 3, 60 } }; int N = mat.GetLength(0); int M = mat.GetLength(1); // Function call to print the matrix // in column wise sorted manner SortCol(mat, N, M); } } // This code is contributed by phasing17. |
Javascript
<script> // JavaScript program for the above approach // Function to find the transpose // of the matrix mat[] function transpose(mat,row,col) { // Stores the transpose // of matrix mat[][] let tr = new Array(col); for (let i=0;i<col;i++) { tr[i]= new Array(row); } // Traverse each row of the matrix for (let i = 0; i < row; i++) { // Traverse each column of the matrix for (let j = 0; j < col; j++) { // Transpose matrix elements tr[j][i] = mat[i][j]; } } return tr; } // Function to sort the given // matrix in row wise manner function RowWiseSort(B) { // Traverse the row for (let i = 0; i < B.length; i++) { // Row - Wise Sorting (B[i]).sort( function (a,b){ return a-b;}); } } // Function to print the matrix // in column wise sorted manner function sortCol(mat,n,M) { // Function call to find transpose // of the matrix mat[][] let B = transpose(mat, N, M); // Sorting the matrix row-wise RowWiseSort(B); // Calculate transpose of B[][] mat = transpose(B, M, N); // Print the matrix mat[][] for (let i = 0; i < N; i++) { for (let j = 0; j < M; j++) { document.write(mat[i][j] + " " ); } document.write( "<br>" ); } } // Driver Code let mat = [[ 1, 6, 10 ], [ 8, 5, 9 ], [ 9, 4, 15 ], [ 7, 3, 60 ] ]; let N = mat.length; let M = mat[0].length; // Function call to print the matrix // in column wise sorted manner sortCol(mat, N, M); // This code is contributed by avanitrachhadiya2155 </script> |
Output:
1 3 9 7 4 10 8 5 15 9 6 60
Time Complexity: O(N * M)
Auxiliary Space: O(N * M)
Contact Us