Given a matrix mat[][] of size M x N integers where M is the number of rows and N is the number of columns and a number K. The task is to sort the Kth column of the matrix. Where K <= N.
Example:
Input: mat[3][3] = {{ 9, 3, 4}, { 5, 2, 7}, { 3, 1, 8}} K = 2 Output: mat[3][3] = {{ 9, 3, 4}, { 2, 5, 7}, { 3, 1, 8}} Explanation: Here, K = 2 so sort the second column(3, 5, 1) to (1, 3, 5) Input: mat[4][2] = {{4, 3}, {6, 9}, {1, 0}, {2, 3}} K = 1 Output: mat[4][2] = {{1, 3}, {2, 9}, {4, 0}, {6, 3}}
RECOMMENDED: Characteristics or features of an Algorithm
Approach:
For Kth column in the given Matrix do the following:
- Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in wrong order.
- Iterate loop 0 to M-1, swap the value at these indexes and update the index as:
- if(mat[j][k-1]>mat[j+1][k-1])
- swap(mat[j][k-1], mat[j+1][k-1])
- if(mat[j][k-1]>mat[j+1][k-1])
Below is the implementation of the above approach:
// C++ implementation of the above approach #include<bits/stdc++.h> using namespace std; const int M = 4; const int N = 2; // A utility function // to swap the two element void swap(int * a, int * b) { int temp = * a; * a = * b; * b = temp; } // Function to sort // the Kth column of the matrix void sortKthColumn(int mat[M][N], int k) { // Bubble sort for (int i = 0; i < M - 1; i++) // Last i elements are already in place for (int j = 0; j < M - i - 1; j++) if (mat[j][k - 1] > mat[j + 1][k - 1]) swap( & mat[j][k - 1], & mat[j + 1][k - 1]); // Print the mat[][] after // sorting Kth column cout << "mat[" << M << "][" << N << "] = {" << endl; for (int i = 0; i < M; i++) { cout << "{ "; for (int j = 0; j < N; j++) { cout << mat[i][j] << ", "; } cout << "}," << endl; } cout << "}," << endl; } // Driver Code int main() { int mat[][2] = { { 4, 3 }, { 6, 9 }, { 1, 0 }, { 2, 3 } }; int K = 1; // Function call sortKthColumn(mat, K); return 0; }
Output:
mat[4][2] = { { 1, 3, }, { 2, 9, }, { 4, 0, }, { 6, 3, }, },
Time Complexity: O(m^2)
Space Complexity: O(1)
Please write comments below if you find anything incorrect, or you want to share more information about the topic discussed above. A gentle request to share this topic on your social media profile.