Given a square matrix of order N*N having distinct elements, the task is to sort given matrix in such a way that its rows, columns and both diagonals (diagonal and anti-diagonal) are in increasing order.
Examples:
Input : arr[3][3] = {1, 4, 2,
3, 5, 6,
9, 7, 8}
Output :{1, 2, 3,
4, 5, 6,
7, 8, 9}
Input : arr[2][2] = {0, 4,
5, 2}
Output :{0, 2,
4, 5}
Sorting any matrix in a way that its rows, columns and main diagonal are in increasing order is easy. If we consider matrix elements in sequence according to row-major order and sort the sequence, we get the desired result.
Example: arr[2][2] : {1, 2
3, 4}
Rows in increasing order: {1,2} and {3,4}
Columns in increasing order: {1,3} and {2,4}
Diagonal in increasing order: {1,4}
Anti-diagonal in increasing order: {2,3}
// C++ program to sort matrix in all-way #include<bits/stdc++.h> using namespace std; #define N 3 // Sorts a matrix in increasing order void sortAllWay(int arr[][N]) { // Consider matrix elements (in row major // order) and sort the sequence. int *ptr = (int *)arr; sort(ptr, ptr+N*N); } // driver program int main() { int arr[N][N] = {1, 0, 3, 2, 5, 6, 9, 4, 8}; sortAllWay(arr); // print resultant matrix for (int i=0; i<N; i++) { for (int j=0; j<N; j++) cout << arr[i][j] << " "; cout <<"
"; } return 0; } |
Output:
0 1 2 3 4 5 6 8 9
Time Complexity : O(N*N log N)
Auxiliary Space : (N*N)
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
leave a comment
0 Comments