Sort the major diagonal of the matrix
Given a matrix mat[][], the task is to sort the main diagonal elements of the matrix in increasing order.
Main Diagonal: Main diagonal or major diagonal of a matrix is the collection of elements mati, j, where i == j.
Examples:
Input: mat[][] = {{4, 2}, {3, 1}} Output: 1 2 3 4 Explanation: In the given matrix, the diagonal elements are - => {mat[0][0], mat[1][1]} => {4, 1} => Sorted Order = {1, 4} Input: mat[][] = {{9, 4}, {3, 4}} Output: 4 4 3 9 Explanation: In the given matrix, the diagonal elements are - => {mat[0][0], mat[1][1]} => {9, 4} => Sorted Order = {4, 9}
Method 1 :-
Approach: The idea is modify the selection sort to sort the diagonal elements of the matrix. Count of the diagonal elements of matrix M*N will be min(M, N). As we know the major diagonal elements of the matrix are mati, j where i == j. Therefore, the ith element of the major diagonal of the matrix will be mat[i][i]. Hence, repeatedly find the minimum element from the major diagonal of the matrix and put it at the beginning.
Below is the implementation of the above approach:
C++
// C++ implementation to sort the // major diagonal of the matrix #include <bits/stdc++.h> using namespace std; // Function to sort the major // diagonal of the matrix void sortDiagonal( int a[2][2], int M, int N) { // Loop to find the ith minimum // element from the major diagonal for ( int i = 0; i < M; i++) { int sm = a[i][i]; int pos = i; // Loop to find the minimum // element from the unsorted matrix for ( int j = i + 1; j < N; j++) { if (sm > a[j][j]) { sm = a[j][j]; pos = j; } } // Swap to put the minimum // element at the beginning of // the major diagonal of matrix swap(a[i][i], a[pos][pos]); } // Loop to print the matrix for ( int i = 0; i < M; i++) { for ( int j = 0; j < N; j++) cout << a[i][j] << " " ; cout << endl; } } // Driven Code int main() { int a[2][2] = { { 4, 2 }, { 3, 1 } }; // Sort the major Diagonal sortDiagonal(a, 2, 2); return 0; } |
Java
// Java implementation to sort the // major diagonal of the matrix class GFG{ // Function to sort the major // diagonal of the matrix static void sortDiagonal( int a[][], int M, int N) { // Loop to find the ith minimum // element from the major diagonal for ( int i = 0 ; i < M; i++) { int sm = a[i][i]; int pos = i; // Loop to find the minimum // element from the unsorted matrix for ( int j = i + 1 ; j < N; j++) { if (sm > a[j][j]) { sm = a[j][j]; pos = j; } } // Swap to put the minimum // element at the beginning of // the major diagonal of matrix swap(a, i, i, pos, pos); } // Loop to print the matrix for ( int i = 0 ; i < M; i++) { for ( int j = 0 ; j < N; j++) System.out.print(a[i][j]+ " " ); System.out.println(); } } static void swap( int [][] a, int i, int i2, int pos, int pos2) { int temp = a[i][i2]; a[i][i2] = a[pos][pos2]; a[pos][pos2] = temp; } // Driven Code public static void main(String[] args) { int a[][] = { { 4 , 2 }, { 3 , 1 } }; // Sort the major Diagonal sortDiagonal(a, 2 , 2 ); } } // This code is contributed by 29AjayKumar |
Python3
# Python3 implementation to sort the # major diagonal of the matrix # Function to sort the major # diagonal of the matrix def sortDiagonal(a, M, N): # Loop to find the ith minimum # element from the major diagonal for i in range (M): sm = a[i][i] pos = i # Loop to find the minimum # element from the unsorted matrix for j in range (i + 1 , N): if (sm > a[j][j]): sm = a[j][j] pos = j # Swap to put the minimum # element at the beginning of # the major diagonal of matrix a[i][i], a[pos][pos] = a[pos][pos] , a[i][i] # Loop to print the matrix for i in range (M): for j in range (N): print (a[i][j],end = " " ) print () # Driven Code a = [[ 4 , 2 ],[ 3 , 1 ]] # Sort the major Diagonal sortDiagonal(a, 2 , 2 ) # This code is contributed by shubhamsingh10 |
C#
// C# implementation to sort the // major diagonal of the matrix using System; class GFG{ // Function to sort the major // diagonal of the matrix static void sortDiagonal( int [,]a, int M, int N) { // Loop to find the ith minimum // element from the major diagonal for ( int i = 0; i < M; i++) { int sm = a[i, i]; int pos = i; // Loop to find the minimum // element from the unsorted matrix for ( int j = i + 1; j < N; j++) { if (sm > a[j, j]) { sm = a[j, j]; pos = j; } } // Swap to put the minimum // element at the beginning of // the major diagonal of matrix swap(a, i, i, pos, pos); } // Loop to print the matrix for ( int i = 0; i < M; i++) { for ( int j = 0; j < N; j++) Console.Write(a[i, j]+ " " ); Console.WriteLine(); } } static void swap( int [,] a, int i, int i2, int pos, int pos2) { int temp = a[i, i2]; a[i, i2] = a[pos, pos2]; a[pos, pos2] = temp; } // Driven Code public static void Main(String[] args) { int [,]a = { { 4, 2 }, { 3, 1 } }; // Sort the major Diagonal sortDiagonal(a, 2, 2); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // Javascript implementation to sort the // major diagonal of the matrix // Function to sort the major // diagonal of the matrix function sortDiagonal(a, M, N) { // Loop to find the ith minimum // element from the major diagonal for ( var i = 0; i < M; i++) { var sm = a[i][i]; var pos = i; // Loop to find the minimum // element from the unsorted matrix for ( var j = i + 1; j < N; j++) { if (sm > a[j][j]) { sm = a[j][j]; pos = j; } } // Swap to put the minimum // element at the beginning of // the major diagonal of matrix temp = a[i][i] a[i][i] = a[pos][pos] a[pos][pos] = temp } // Loop to print the matrix for ( var i = 0; i < M; i++) { for ( var j = 0; j < N; j++) document.write( a[i][j] + " " ); document.write( "<br>" ); } } // Driven Code var a = [ [ 4, 2 ], [ 3, 1 ] ]; // Sort the major Diagonal sortDiagonal(a, 2, 2); // This code is contributed by noob2000. </script> |
1 2 3 4
Performance Analysis:
- Time Complexity: O(min(M, N)2)
- Auxiliary Space: O(1)
Method 2:-
Approach: The idea is to insert all the diagonal elements in a temporary array and simply use sort STL function to sort the diagonal elements
C++
// C++ implementation to sort the // major diagonal of the matrix #include <bits/stdc++.h> using namespace std; // Function to print the matrix void printArray( int a[2][2], int N){ for ( int i = 0; i < N; i++) { for ( int j = 0; j < N; j++) cout << a[i][j] << " " ; cout << endl; } } // Function to sort the major // diagonal of the matrix void sortDiagonal( int a[2][2], int N) { // Temporary vector to store diagonal elements vector < int > diagonalElements; // Storing Diagonal Elements into Temporary Vector for ( int i = 0; i < N; i++) { diagonalElements.push_back(a[i][i]); } // Sort the array diagonal elements sort(diagonalElements.begin(), diagonalElements.end()); // Insert the sorted diagonal elements to the original Array for ( int i = 0; i < N; i++) { a[i][i] = diagonalElements[i]; } } // Driven Code int main() { int a[2][2] = { { 4, 2 }, { 3, 1 } }; // Sort the major Diagonal sortDiagonal(a, 2); //print Array printArray(a, 2); return 0; } |
Java
// Java implementation to sort the // major diagonal of the matrix import java.util.*; class GFG{ // Function to print the matrix static void printArray( int a[][], int N){ for ( int i = 0 ; i < N; i++) { for ( int j = 0 ; j < N; j++) System.out.print(a[i][j]+ " " ); System.out.println(); } } // Function to sort the major // diagonal of the matrix static void sortDiagonal( int a[][], int N) { // Temporary vector to store diagonal elements Vector <Integer> diagonalElements = new Vector<>(); // Storing Diagonal Elements into Temporary Vector for ( int i = 0 ; i < N; i++) { diagonalElements.add(a[i][i]); } // Sort the array diagonal elements Collections.sort(diagonalElements); // Insert the sorted diagonal elements to the original Array for ( int i = 0 ; i < N; i++) { a[i][i] = diagonalElements.get(i); } } // Driven Code public static void main(String[] args) { int [][]a = { { 4 , 2 }, { 3 , 1 } }; // Sort the major Diagonal sortDiagonal(a, 2 ); //print Array printArray(a, 2 ); } } // This code is contributed by 29AjayKumar |
Python3
# Python3 implementation to sort the # major diagonal of the matrix # Function to print the matrix def printArray(a, N): for i in range (N): for j in range (N): print (a[i][j] ,end = " " ) print () # Function to sort the major # diagonal of the matrix def sortDiagonal(a, N): # Temporary vector to store diagonal elements diagonalElements = [] # Storing Diagonal Elements into Temporary Vector for i in range (N): diagonalElements.append(a[i][i]) # Sort the array diagonal elements diagonalElements.sort() # Insert the sorted diagonal elements to the original Array for i in range (N): a[i][i] = diagonalElements[i] # Driven Code a = [ [ 4 , 2 ], [ 3 , 1 ] ] # Sort the major Diagonal sortDiagonal(a, 2 ) # print Array printArray(a, 2 ) # This code is contributed by shinjanpatra |
C#
// C# implementation to sort the // major diagonal of the matrix using System; using System.Collections.Generic; public class GFG{ // Function to print the matrix static void printArray( int [,]a, int N){ for ( int i = 0; i < N; i++) { for ( int j = 0; j < N; j++) Console.Write(a[i,j]+ " " ); Console.WriteLine(); } } // Function to sort the major // diagonal of the matrix static void sortDiagonal( int [,]a, int N) { // Temporary vector to store diagonal elements List < int > diagonalElements = new List< int >(); // Storing Diagonal Elements into Temporary List for ( int i = 0; i < N; i++) { diagonalElements.Add(a[i,i]); } // Sort the array diagonal elements diagonalElements.Sort(); // Insert the sorted diagonal elements to the original Array for ( int i = 0; i < N; i++) { a[i,i] = diagonalElements[i]; } } // Driven Code public static void Main(String[] args) { int [,]a = { { 4, 2 }, { 3, 1 } }; // Sort the major Diagonal sortDiagonal(a, 2); //print Array printArray(a, 2); } } // This code is contributed by shikhasingrajput |
Javascript
<script> // JavaScript implementation to sort the // major diagonal of the matrix // Function to print the matrix function printArray(a, N){ for (let i = 0; i < N; i++) { for (let j = 0; j < N; j++) document.write(a[i][j], " " ); document.write( "</br>" ) } } // Function to sort the major // diagonal of the matrix function sortDiagonal(a, N) { // Temporary vector to store diagonal elements let diagonalElements = []; // Storing Diagonal Elements into Temporary Vector for (let i = 0; i < N; i++) { diagonalElements.push(a[i][i]); } // Sort the array diagonal elements diagonalElements.sort(); // Insert the sorted diagonal elements to the original Array for (let i = 0; i < N; i++) { a[i][i] = diagonalElements[i]; } } // Driven Code let a = [ [ 4, 2 ], [ 3, 1 ] ]; // Sort the major Diagonal sortDiagonal(a, 2); //print Array printArray(a, 2); // This code is contributed by shinjanpatra </script> |
1 2 3 4
Performance Analysis:
- Time Complexity: O(N*log(N)) ; as we traversed the array to find diagonals in one loop O(N) and to sort the temporary vector it required O(N*log(N))
- Auxiliary Space: O(N) ; as we used a temporary vector for the purpose of sorting
Contact Us