Tutorialspoint.dev

Sort a Matrix in all way increasing order

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.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter