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}
Implementation:
CPP
// 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 <<"\n"; } return 0; } |
Java
// Java program to sort matrix in all-way import java.util.*; class GFG{ static final int N = 3; // Sorts a matrix in increasing order static int[][] sortAllWay(int arr[][]) { // Consider matrix elements (in row major // order) and sort the sequence. int []ar = new int[arr.length*arr.length]; int k = 0; for(int i = 0; i < arr.length; i++) { for(int j = 0; j < arr.length; j++) { ar[k] = arr[i][j]; k++; } } Arrays.sort(ar); k = 0; for(int i = 0; i < arr.length; i++) { for(int j = 0; j < arr.length; j++) { arr[i][j] = ar[k]; k++; } } return arr; } // Driver program public static void main(String[] args) { int arr[][] = {{1, 0, 3}, { 2, 5, 6}, { 9, 4, 8}}; arr = sortAllWay(arr); // print resultant matrix for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) System.out.print(arr[i][j] + " "); System.out.println(); } } } // This code is contributed by umadevi9616 |
Python3
# Python program to sort matrix in all-way N = 3; # Sorts a matrix in increasing order def sortAllWay(arr): # Consider matrix elements (in row major # order) and sort the sequence. ar = [0 for i in range(len(arr) * len(arr))]; k = 0; for i in range(len(arr)): for j in range(len(arr)): ar[k] = arr[i][j]; k += 1; ar.sort(); k = 0; for i in range(len(arr)): for j in range(len(arr)): arr[i][j] = ar[k]; k += 1; return arr; # Driver program if __name__ == '__main__': arr = [[ 1, 0, 3 ],[ 2, 5, 6 ],[ 9, 4, 8 ]] ; arr = sortAllWay(arr); # print resultant matrix for i in range(N): for j in range(N): print(arr[i][j], end=" "); print(); # This code IS contributed by umadevi9616 |
C#
// C# program to sort matrix in all-way using System; public class GFG { static readonly int N = 3; // Sorts a matrix in increasing order static int[,] sortAllWay(int [,]arr) { // Consider matrix elements (in row major // order) and sort the sequence. int[] ar = new int[arr.GetLength(0) * arr.GetLength(1)]; int k = 0; for (int i = 0; i < arr.GetLength(0); i++) { for (int j = 0; j < arr.GetLength(1); j++) { ar[k] = arr[i,j]; k++; } } Array.Sort(ar); k = 0; for (int i = 0; i < arr.GetLength(0); i++) { for (int j = 0; j < arr.GetLength(1); j++) { arr[i,j] = ar[k]; k++; } } return arr; } // Driver program public static void Main(String[] args) { int [,]arr = { { 1, 0, 3 }, { 2, 5, 6 }, { 9, 4, 8 } }; arr = sortAllWay(arr); // print resultant matrix for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) Console.Write(arr[i,j] + " "); Console.WriteLine(); } } } // This code is contributed by umadevi9616 |
Javascript
<script> // Javascript program to sort matrix in all-way var N = 3; // Sorts a matrix in increasing order function sortAllWay(arr) { // Consider matrix elements (in row major // order) and sort the sequence. arr.sort((a,b)=>a-b); return arr; } // driver program var arr = [1, 0, 3, 2, 5, 6, 9, 4, 8]; arr = sortAllWay(arr); // print resultant matrix for(var i=0; i<N; i++) { for (var j=0; j<N; j++) document.write(arr[N*i+j] + " "); document.write("<br>"); } // This code is contributed by rutvik_56. </script> |
Output
0 1 2 3 4 5 6 8 9
Time Complexity : O(N*N log N)
Auxiliary Space : (N*N), since N*N extra space has been taken.
This article is contributed by Shivam Pradhan. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
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!
