Given a matrix arr[][] of dimensions N * M, the task is to sort the matrix such that each row is sorted and the first element of each row is greater than or equal to the last element of the previous row.
Examples:
Input: N = 3, M = 3, arr[][] = {{7, 8, 9}, {5, 6, 4}, {3, 1, 2}}
Output:
1 2 3
4 5 6
7 8 9
Approach: Follow the steps below to solve the problem:
- Traverse the matrix
- For every matrix element, consider it to be the minimum element in the matrix. Check if there is a smaller element present in the rest of the matrix.
- If found to be true, swap the current element and the minimum element in the matrix.
- Finally, print the sorted matrix.
Below is the implementation for the above approach:
C
// C program for the above approach #include <stdio.h> #include <stdlib.h> #define SIZE 100 // Function to sort a matrix void sort_matrix(int arr[SIZE][SIZE], int N, int M) { // Traverse over the matrix for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { // Current minimum element int minimum = arr[i][j]; // Index of the current // minimum element int z = i; int q = j; // Check if any smaller element // is present in the matrix int w = j; for (int k = i; k < N; k++) { for (; w < M; w++) { // Update the minimum element if (arr[k][w] < minimum) { minimum = arr[k][w]; // Update the index of // the minimum element z = k; q = w; } } w = 0; } // Swap the current element // and the minimum element int temp = arr[i][j]; arr[i][j] = arr[z][q]; arr[z][q] = temp; } } } // Function to print the sorted matrix void printMat(int arr[SIZE][SIZE], int N, int M) { for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { printf("%d ", arr[i][j]); } printf("\n"); } } // Driver Code int main() { int N = 3, M = 3; int arr[SIZE][SIZE] = { { 7, 8, 9 }, { 5, 6, 4 }, { 3, 1, 2 } }; // Sort the matrix sort_matrix(arr, N, M); // Print the sorted matrix printMat(arr, N, M); return 0; } |
Output:
1 2 3 4 5 6 7 8 9
Time Complexity: O(N4)
Auxiliary Space: O(1)
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!
