Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
2.1.
Examples:
2.2.
Approach:
3.
Algorithm for sorting each row of matrix using Java Collections:
4.
Algorithm for transposing the matrix:
5.
Program in Java
5.1.
Output:
6.
Program in  C++
6.1.
Output
7.
Program in Python
8.
Output
9.
Frequently Asked Questions
9.1.
Is it possible to sort a collection in Java?
9.2.
Which sorting method is the quickest?
9.3.
What is the matrix's order of operations?
9.4.
What exactly does "merge sort" imply?
10.
Conclusion
Last Updated: Mar 27, 2024
Easy

Sort the matrix row-wise and column-wise

Author Ayush Mishra
0 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

A matrix is a useful tool for quickly approximating complex calculations in computer science and mathematics. A matrix is a rectangular table or array of numbers, symbols, or expressions that are organized in rows and columns to represent a mathematical object or an attribute of such an object in mathematics.

In this article, we'll look at how to sort the matrix rows and columns by value. We'll go through the ideas, techniques, and examples of Sorting a matrix by row and column and how to implement them in various programming languages.

Problem Statement

The problem states we are given a n x n matrix. The current assignment entails sorting the matrix by row and column.

Examples:

Input : marix[][] =  {
 {5, 2, 3},
 {8, 5, 7},
 {6, 4, 8} 
 }
                    
Output :
 2 3 5
 4 6 8
 5 7 8


Input : matrix[][] ={ 
{12, 7, 1, 8},
{20, 9, 11, 2},
{15, 4, 5, 13},
{3, 18, 10, 6} 
} 
                       
Output :
 1 5 8 12
 2 6 10 15
 3 7 11 18
 4 9 13 20

Approach:

The steps are as follows:

  1. Sort each row of the given matrix.
  2. Get transpose of the matrix.
  3. Sort each row of the matrix again.
  4. Transpose the matrix again.
  5. Print the matrix before and after sorting the matrix.
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Algorithm for sorting each row of matrix using Java Collections:

for (int i = 0; i < n; i++) 
            Arrays.sort(matrix[i]); 

Algorithm for transposing the matrix:

for (int x = 0; x < n; x++) {
    for (int y = x+ 1; y < n; y++) {
        int t = matrix[x][y];
        mat[x][y] = mat[y][x];
        mat[y][x] = t;
    }
}

Program in Java

//Java implementation to sort the matrix row-wise and column-wise 
import java.util.*; 
class Sort_Matrix 
{ 
    static final int MAX_SIZE=12; 
      
    // Each row of the matrix is sorted using below function.
    static void sortMatrixByRow(int matrix[][], int n) 
    { 
        for (int i = 0; i < n; i++) 
            Arrays.sort(matrix[i]); 
    } 
    // function to find transpose of the matrix 
    static void transpose(int matrix[][], int n) 
    { 
        for (int i = 0; i < n; i++) 
         {
            for (int j = i + 1; j < n; j++)  
                { 
                int temp=matrix[i][j]; 
                matrix[i][j]=matrix[j][i]; 
                matrix[j][i]=temp; 
                } 
          }
    } 
      
    // function to sort the matrix row-wise and column-wise 
    
    static void sortMatRowAndColWise(int matrix[][],int n) 
    { 
        sortMatrixByRow(matrix, n); // sort rows of matrix[][] 
        transpose(matrix, n);  // get transpose of matrix[][] 
        sortMatrixByRow(matrix, n); // again sort rows of matrix[][] 
        transpose(matrix, n); // again get transpose of matrix[][] 
    } 
    // function to print the matrix 
    static void printMatrix(int matrix[][], int n) 
    { 
        for (int i = 0; i < n; i++)
         { 
            for (int j = 0; j < n; j++) 
            {
                System.out.print(matrix[i][j] + " "); 
            }
            System.out.println(); 
        } 
    }  
    public static void main (String[] args) 
    { 
        int matrix[][] = { { 5, 2, 3 }, 
                           { 8, 5, 7 }, 
                           { 6, 4, 8 } }; 
        int n = 3; 
      
        System.out.println("Matrix before Sorting:"); 
        printMatrix(matrix, n); 
        sortMatRowAndColWise(matrix, n); 
        System.out.println("Matrix After Sorting:"); 
        printMatrix(matrix, n); 
    } 
}   

Output:

Matrix before Sorting:
5 2 3 
8 5 7 
6 4 8 
Matrix After Sorting:
2 3 5 
4 6 8 
5 7 8 

Program in  C++

// Sorting the matrix row-by-row and column-by-column in C++
#include <bits/stdc++.h>
using namespace std;
#define M_SIZE 12
 
// Sort each row of the matrix with given below function
void sortByRow(int matrix[M_SIZE][M_SIZE], int n)
{
for (int i = 0; i < n; i++)
sort(matrix[i], matrix[i] + n);
}
 
// function to find the matrix's transpose
void transpose(int matrix[M_SIZE][M_SIZE], int n)
{
	for (int i = 0; i < n; i++)
	{
		for (int j = i + 1; j < n; j++)
 			{
				swap(matrix[i][j], matrix[j][i]);
			}
	}
}
// function to sort the matrix row-wise and column-wise
void sortMatRowAndColWise(int matrix[M_SIZE][M_SIZE],int n)
{
// sort rows of matrix[][]
sortByRow(matrix, n); 
// get transpose of matrix[][]
transpose(matrix, n); 
// again sort rows of matrix[][]
sortByRow(matrix, n); 
// again get transpose of matrix[][]
transpose(matrix, n);
}
 
// function to print the matrix
void printMatrix(int matrix[M_SIZE][M_SIZE], int n)
{
	for (int i = 0; i < n; i++) 
		{
		for (int j = 0; j < n; j++)
			{
			cout << matrix[i][j] << " ";
			}
		cout << endl;
		}
}


int main()
{
int matrix[M_SIZE][M_SIZE] ={ { 5, 2, 3 }, 
                              { 8, 5, 7 }, 
                              { 6, 4, 8 } }; 


int n=3;
 
cout << "Matrix before Sorting:"<<endl;
printMatrix(matrix, n); 
sortMatRowAndColWise(matrix, n); 
cout << "Matrix After Sorting:"<<endl;
printMatrix(matrix, n); 
return 0;
}

Output

Matrix before Sorting:
5 2 3 
8 5 7 
6 4 8 
Matrix After Sorting:
2 3 5 
4 6 8 
5 7 8 

Program in Python

MAX_SIZE = 11
#Each row of the matrix is sorted using the below function.


def sortMatrixByRow(matrix, n):
for i in range (n):
	for j in range(n-1):
		if matrix[i][j] > matrix[i][j + 1]:
			t = matrix[i][j]
			matrix[i][j] = matrix[i][j + 1]
			matrix[i][j + 1] = t

# function to find the matrix's transpose

def transpose(matrix, n):
	for i in range (n):
		for j in range(i + 1, n):
# swapping element at index (i, j) by element at index (j, i)
			t = matrix[i][j]
			matrix[i][j] = matrix[j][i]
			matrix[j][i] = t

# function to sort the matrix row-wise and column-wise

def sortMatRowAndColWise(matrix, n):
	sortMatrixByRow(matrix, n)  # sort rows of matrix[][]
	transpose(matrix, n)    # get transpose of matrix[][]
	sortMatrixByRow(matrix, n)  # again sort rows of matrix[][]
	transpose(matrix, n)    # again transpose the matrix[][]
    
# function to print the matrix

def printMatrix(matrix, n):
	for i in range(n):
		for j in range(n):
			print(str(matrix[i][j] ), end = " ")
		print();
matrix = [[ 9, 0, 0 ],
[ 5, 2, 6 ],
[ 8, 6, 7 ]]
n = 3

print("Matrix before sorting :")
printMatrix(matrix, n)
sortMatRowAndColWise(matrix, n)
print("\nMatrix After Sorting:")
printMatrix(matrix, n)

Output

Matrix before Sorting:
9 0 0 
5 2 6 
8 6 7 
Matrix After Sorting:
0 0 6 
2 5 8 
6 7 9


Time Complexity: O(n^2log2n). 

Auxiliary Space: O(1).

Also see,  Rabin Karp Algorithm

Refer to know about :  Topological sort

Frequently Asked Questions

Is it possible to sort a collection in Java?

The sort() function is available in the util. Collections class in Java. It's used to sort the elements in a Collection's provided list in ascending order.

Which sorting method is the quickest?

One of the most efficient sorting algorithms is Quicksort, and hence one of the most often utilized.

What is the matrix's order of operations?

The order of a matrix is expressed as m×n, where m signifies the number of rows and n the  number of columns..

What exactly does "merge sort" imply?

The Divide and Conquer method is used in Merge Sort. It divides the input array into two halves, then calls itself for each half before merging the two sorted halves.

Conclusion

We have discuss to solve the problem row and column-wise sorting in the matrix. Now, grasping a new idea always excites one, and this enthusiasm motivates one to study other concepts. We're also here to help you with that.

We hope this blog has taught you something new. Also read our blogs on Operations on MatricesConstruct a Linked List from a 2D Matrix, Matrix Chain Multiplication, and Types of Matrix for additional information.

Recommended Problems - 


Please vote for our site in order to assist other ninjas in achieving their goals.

Close your eyes and go to Coding Ninjas Studio to practice top problems, take sample examinations, read interview stories, etc.

Happy Learning!

Live masterclass