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