Given a matrix of N rows and M columns, the task is to sort the matrix in the strict order that is every row is sorted in increasing order and the first element of every row is greater than the first element of the previous row.
Examples:
Input: M[][] = { {5, 4, 7},
{1, 3, 8},
{2, 9, 6} }
Output: 1 2 3
4 5 6
7 8 9
Explanation:
Please refer above image
Input: M[][] = { {5, 4, 7},
{1, 3, 8} }
Output: 1 3 4
5 7 8
Approach: The idea is to treat the 2D-Array as a 1D-Array to sort the matrix without using extra space. This can also be explained with the help of the following example.
For Example:
There is a 2*2 Matrix with 4 elements, The idea is to treat the elements of the matrix as 1D Array of 4 elements. 1 2 3 4 As In the given matrix each element can be accessed as - 1st Element - 0th Row, 0th Col 2nd Element - 0th Row, 1st Col 3rd Element - 1st Row, 0th Col 4th Element - 1st Row, 1st Col
So, for Accessing ith element of the matrix, the relation can be defined as:
Ith Element of the Matrix = Mat[ i / cols ][ i % cols ]
Algorithm:
- Find the number of rows(say rows) and columns(say cols) in the matrix by finding the length of the number of rows in the 2D-Array and the elements in each row in the Array.
- Iterate over each element of the matrix from 0 to the number of elements (rows * cols).
- Find the appropriate position of the element in the matrix using the above formulae for each element.
- Compare each element with the next element (For the last element in the row, the next element will be the next row first element) in the matrix, and if the next element is, less then swap these elements.
Illustration with Example:
| I | J | Comparison Elements | Matrix | Comments |
|---|---|---|---|---|
| 0 | 0 | (0, 0) & (0, 1) | 5 6 7 1 4 8 |
No Swap |
| 0 | 1 | (0, 1) & (0, 2) | 5 6 7 1 4 8 |
No Swap |
| 0 | 2 | (0, 2) & (1, 0) | 5 6 1 7 4 8 |
Swapped |
| 0 | 3 | (1, 0) & (1, 1) | 5 6 1 4 7 8 |
Swapped |
| 0 | 4 | (1, 1) & (1, 2) | 5 6 1 4 7 8 |
No Swap |
| 1 | 0 | (0, 0) & (0, 1) | 5 6 1 4 7 8 |
No Swap |
| 1 | 1 | (0, 1) & (0, 2) | 5 1 6 4 7 8 |
Swapped |
| 1 | 2 | (0, 2) & (1, 0) | 5 1 4 6 7 8 |
Swapped |
| 1 | 3 | (1, 0) & (1, 1) | 5 1 4 6 7 8 |
No Swap |
| 1 | 4 | (1, 1) & (1, 2) | 5 1 4 4 7 8 |
No Swap |
| 2 | 0 | (0, 0) & (0, 1) | 1 5 4 6 7 8 |
Swapped |
| 2 | 1 | (0, 1) & (0, 2) | 1 4 5 6 7 8 |
Swapped |
| 2 | 2 | (0, 2) & (1, 0) | 1 4 5 6 7 8 |
No Swap |
| 2 | 3 | (1, 0) & (1, 1) | 5 1 4 6 7 8 |
No Swap |
| 2 | 4 | (1, 1) & (1, 2) | 5 1 4 4 7 8 |
No Swap |
Below is the implementation of the above approach:
C++
// C++ implementation to sort // the given matrix in strict order #include <bits/stdc++.h> using namespace std; #define N 3 #define M 3 // Function to sort the matrix void sortMat(int data[N][M], int row, int col) { // Number of elements in matrix int size = row * col; // Loop to sort the matrix // using Bubble Sort for (int i = 0; i < size; i++) { for (int j = 0; j < size - 1; j++) { // Condition to check // if the Adjacent elements if (data[j / col][j % col] > data[(j + 1) / col][(j + 1) % col]) { // Swap if previous value is greater int temp = data[j / col][j % col]; data[j / col][j % col] = data[(j + 1) / col][(j + 1) % col]; data[(j + 1) / col][(j + 1) % col] = temp; } } } } void printMat(int mat[N][M], int row, int col) { // Loop to print the matrix for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { cout << mat[i][j] << " "; } cout << endl; } } // Driver Code int main() { int mat[N][M] = { { 5, 4, 7 }, { 1, 3, 8 }, { 2, 9, 6 } }; int row = N; int col = M; // Function call to sort sortMat(mat, row, col); // Function call to // print matrix printMat(mat, row, col); return 0; } // This code is contributed by 29AjayKumar |
Java
// Java implementation to sort // the given matrix in strict order class GFG { // Function to sort the matrix static void sortMat(int[][] data, int row, int col) { // Number of elements in matrix int size = row * col; // Loop to sort the matrix // using Bubble Sort for (int i = 0; i < size; i++) { for (int j = 0; j < size - 1; j++) { // Condition to check // if the Adjacent elements if (data[j / col][j % col] > data[(j + 1) / col][(j + 1) % col]) { // Swap if previous value is greater int temp = data[j / col][j % col]; data[j / col][j % col] = data[(j + 1) / col][(j + 1) % col]; data[(j + 1) / col][(j + 1) % col] = temp; } } } } static void printMat(int[][] mat, int row, int col) { // Loop to print the matrix for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { System.out.print(mat[i][j] + " "); } System.out.println(); } } // Driver Code public static void main(String[] args) { int[][] mat = { { 5, 4, 7 }, { 1, 3, 8 }, { 2, 9, 6 } }; int row = mat.length; int col = mat[0].length; // Function call to sort sortMat(mat, row, col); // Function call to // print matrix printMat(mat, row, col); } } // This code is contributed by PrinciRaj1992 |
Python3
# Python3 implementation to sort # the given matrix in strict order # Function to sort the matrix def sortMat(data, row, col): # Number of elements in matrix size = row * col # Loop to sort the matrix # using Bubble Sort for i in range(0, size): for j in range(0, size-1): # Condition to check # if the Adjacent elements if ( data[j//col][j % col] >\ data[(j + 1)//col][(j + 1)% col] ): # Swap if previous value is greater temp = data[j//col][j % col] data[j//col][j % col] =\ data[(j + 1)//col][(j + 1)% col] data[(j + 1)//col][(j + 1)% col] =\ temp def printMat(mat, row, col): # Loop to print the matrix for i in range(row): for j in range(col): print(mat[i][j], end =" ") print() # Driver Code if __name__ == "__main__": mat = [ [5, 4, 7], [1, 3, 8], [2, 9, 6] ] row = len(mat) col = len(mat[0]) # Function call to sort sortMat(mat, row, col) # Function call to # print matrix printMat(mat, row, col) |
C#
// C# implementation to sort // the given matrix in strict order using System; class GFG { // Function to sort the matrix static void sortMat(int[,] data, int row, int col) { // Number of elements in matrix int size = row * col; // Loop to sort the matrix // using Bubble Sort for (int i = 0; i < size; i++) { for (int j = 0; j < size - 1; j++) { // Condition to check // if the Adjacent elements if (data[j / col,j % col] > data[(j + 1) / col,(j + 1) % col]) { // Swap if previous value is greater int temp = data[j / col,j % col]; data[j / col,j % col] = data[(j + 1) / col,(j + 1) % col]; data[(j + 1) / col,(j + 1) % col] = temp; } } } } static void printMat(int[,] mat, int row, int col) { // Loop to print the matrix for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { Console.Write(mat[i,j] + " "); } Console.WriteLine(); } } // Driver Code public static void Main(String[] args) { int[,] mat = { { 5, 4, 7 }, { 1, 3, 8 }, { 2, 9, 6 } }; int row = mat.GetLength(0); int col = mat.GetLength(1); // Function call to sort sortMat(mat, row, col); // Function call to // print matrix printMat(mat, row, col); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // Javascript implementation to sort // the given matrix in strict order let N = 3; let M = 3; // Function to sort the matrix function sortMat(data, row, col) { // Number of elements in matrix let size = row * col; // Loop to sort the matrix // using Bubble Sort for (let i = 0; i < size; i++) { for (let j = 0; j < size - 1; j++) { // Condition to check // if the Adjacent elements if (data[(Math.floor(j / col))][j % col] > data[(Math.floor((j + 1) / col))][(j + 1) % col]) { // Swap if previous value is greater let temp = data[(Math.floor(j / col))][j % col]; data[(Math.floor(j / col))][j % col] = data[(Math.floor((j + 1) / col))][(j + 1) % col]; data[(Math.floor((j + 1) / col))][(j + 1) % col] = temp; } } } } function printMat(mat, row, col) { // Loop to print the matrix for (let i = 0; i < row; i++) { for (let j = 0; j < col; j++) { document.write(mat[i][j] + " "); } document.write("<br>"); } } // Driver Code let mat = [ [ 5, 4, 7 ], [ 1, 3, 8 ], [ 2, 9, 6 ] ]; let row = N; let col = M; // Function call to sort sortMat(mat, row, col); // Function call to // print matrix printMat(mat, row, col); // This code is contributed by gfgking </script> |
Output:
1 2 3 4 5 6 7 8 9
Performance Analysis:
- Time Complexity: In the given approach, we are sorting the elements in the matrix by considering the elements in the 1D-Array using Bubble sort, so the overall complexity will be O(N * M>)
- Space Complexity: In the given approach, no extra space is used, so the overall space complexity will be O(1)
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!
