Sort matrix elements
The problem is to sort the elements of a given 2D matrix in ascending order. The input is a matrix, and we need to rearrange its elements in such a way that each row and each column of the matrix are sorted in non-decreasing order.
Example
Consider the following 2D matrix:
2 6 9 5
13 7 16 15
45 14 6 82
54 55 4 18
1 6 12 19
7 51 12 3
41 19 8 50
The sorted matrix will be:
1 2 3 4
5 6 6 6
7 7 8 9
12 12 13 14
15 16 18 19
19 41 45 50
51 54 55 82
Idea to Solve the Problem
To sort the matrix elements, we can perform the following steps:
- Collect all the elements of the matrix and store them in a 1D auxiliary array.
- Sort the auxiliary array using a sorting algorithm. In this code, we use the Merge Sort algorithm for sorting.
- Update the matrix with elements from the sorted auxiliary array.
Algorithm
- Create a function
printMatrix
to display the elements of the matrix. - Create a function
mergeElements
to merge two sorted subarrays of the auxiliary array. - Create a function
mergeSort
to perform the Merge Sort on the auxiliary array. - Create a function
sortMatrix
to sort the matrix elements using the auxiliary array. - In the
main
function, define the 2D matrix and its dimensions. - Display the original matrix.
- Call the
sortMatrix
function to sort the matrix elements. - Display the sorted matrix.
Pseudocode
sortMatrix(matrix, row, col):
size = row * col
if size <= 0:
return
Create an auxiliary array 'auxiliary' of size 'size'
k = 0
for i from 0 to row-1:
for j from 0 to col-1:
auxiliary[k] = matrix[i][j]
k = k + 1
mergeSort(auxiliary, 0, size - 1)
k = 0
for i from 0 to row-1:
for j from 0 to col-1:
matrix[i][j] = auxiliary[k]
k = k + 1
mergeSort(auxiliary, front, tail):
if front < tail:
middle = (front + tail) / 2
mergeSort(auxiliary, front, middle)
mergeSort(auxiliary, middle + 1, tail)
mergeElements(auxiliary, front, tail, middle)
mergeElements(auxiliary, front, tail, middle):
s1 = (middle - front) + 1
s2 = tail - middle
Create two temporary arrays 'first_subarray' and 'second_subarray'
Copy elements from auxiliary to first_subarray and second_subarray
i = 0
j = 0
counter = 0
while counter < s1 + s2:
if i < s1 and j < s2:
if first_subarray[i] <= second_subarray[j]:
auxiliary[front + counter] = first_subarray[i]
i = i + 1
else:
auxiliary[front + counter] = second_subarray[j]
j = j + 1
else if i < s1:
auxiliary[front + counter] = first_subarray[i]
i = i + 1
else:
auxiliary[front + counter] = second_subarray[j]
j = j + 1
counter = counter + 1
Code Solution
/*
C program
Sort matrix elements
*/
#include <stdio.h>
// Matrix size
#define R 7
#define C 4
//Displaying of the matrix elements
void printMatrix(int matrix[R][C])
{
int i;
int j;
for (i = 0; i < R; ++i)
{
for (j = 0; j < C; ++j)
{
printf(" %d", matrix[i][j]);
}
printf("\n");
}
printf("\n");
}
//Sorted merge of given two subarrays of an array
void mergeElements(int auxiliary[], int front, int tail, int middle)
{
//Get the size of first subarray
int s1 = (middle - front) + 1;
//Get the size of second subarray
int s2 = tail - middle;
//Creating auxiliary storage to store elements
int first_subarray[s1];
int second_subarray[s2];
//Loop controlling variables
int i = 0;
int j = 0;
int counter = 0;
//Get the elements of first subarray
for (i = 0; i < s1; i++)
{
first_subarray[i] = auxiliary[front + i];
}
//Get the elements of second subarray
for (i = 0; i < s2; i++)
{
second_subarray[i] = auxiliary[middle + i + 1];
}
i = 0;
// Add sorted elements into actual array
while (counter < s1 + s2)
{
//Check that both sub array element exists or not
if (i < s1 && j < s2)
{
if (first_subarray[i] <= second_subarray[j])
{
//When first array [i] element are smaller
auxiliary[front + counter] = first_subarray[i];
i++;
}
else
{
//When second array [j] element are smaller
auxiliary[front + counter] = second_subarray[j];
j++;
}
}
else if (i < s1)
{
//When first sub array element exists
auxiliary[front + counter] = first_subarray[i];
i++;
}
else
{
//When second sub array element exists
auxiliary[front + counter] = second_subarray[j];
j++;
}
counter++;
}
}
// Perform merge sort
// Handles the request of split and merge in array elements
void mergeSort(int auxiliary[], int front, int tail)
{
if (front < tail)
{
//Get middle location of given index
int middle = (front + tail) / 2;
//Split the array into two parts
mergeSort(auxiliary, front, middle);
mergeSort(auxiliary, middle + 1, tail);
//Combine split array into sorted way
mergeElements(auxiliary, front, tail, middle);
}
}
//
void sortMatrix(int matrix[R][C])
{
int size = R *C;
if (size <= 0)
{
return;
}
// This is collecting of matrix elements
int auxiliary[size];
int i = 0;
int j = 0;
int k = 0;
// Collect elements of 2d array
for (i = 0; i < R; ++i)
{
for (j = 0; j < C; ++j)
{
auxiliary[k] = matrix[i][j];
k++;
}
}
mergeSort(auxiliary, 0, size - 1);
k = 0;
// Put sorted elements into matrix
for (i = 0; i < R; ++i)
{
for (j = 0; j < C; ++j)
{
matrix[i][j] = auxiliary[k];
k++;
}
}
}
int main()
{
// Define matrix of an integer elements
int matrix[R][C] =
{
{2, 6, 9 , 5 },
{13, 7, 16 , 15 },
{45, 14, 6, 82 },
{54, 55, 4, 18 },
{1, 6, 12, 19 },
{7, 51, 12, 3 },
{41, 19, 8, 50 }
};
// Before Sort matrix elements
printf("\n Before sorted matrix\n");
printMatrix(matrix);
// Sort matrix elements
sortMatrix(matrix);
//After Sort matrix elements
printf("\n After sorted matrix\n");
printMatrix(matrix);
return 0;
}
Output
Before sorted matrix
2 6 9 5
13 7 16 15
45 14 6 82
54 55 4 18
1 6 12 19
7 51 12 3
41 19 8 50
After sorted matrix
1 2 3 4
5 6 6 6
7 7 8 9
12 12 13 14
15 16 18 19
19 41 45 50
51 54 55 82
/*
Java Program
Sort matrix elements
*/
public class MyMatrix
{
//Displaying of the matrix elements
public void printMatrix(int[][] matrix, int row, int col)
{
int i;
int j;
for (i = 0; i < row; ++i)
{
for (j = 0; j < col; ++j)
{
System.out.print(" " + matrix[i][j] );
}
System.out.print("\n");
}
System.out.print("\n");
}
//Sorted merge of given two subarrays of an array
public void mergeElements(int[] auxiliary, int front, int tail, int middle)
{
//Get the size of first subarray
int s1 = (middle - front) + 1;
//Get the size of second subarray
int s2 = tail - middle;
//Creating auxiliary storage to store elements
int[] first_subarray = new int[s1];
int[] second_subarray = new int[s2];
//Loop controlling variables
int i = 0;
int j = 0;
int counter = 0;
//Get the elements of first subarray
for (i = 0; i < s1; i++)
{
first_subarray[i] = auxiliary[front + i];
}
//Get the elements of second subarray
for (i = 0; i < s2; i++)
{
second_subarray[i] = auxiliary[middle + i + 1];
}
i = 0;
// Add sorted elements into actual array
while (counter < s1 + s2)
{
//Check that both sub array element exists or not
if (i < s1 && j < s2)
{
if (first_subarray[i] <= second_subarray[j])
{
//When first array [i] element are smaller
auxiliary[front + counter] = first_subarray[i];
i++;
}
else
{
//When second array [j] element are smaller
auxiliary[front + counter] = second_subarray[j];
j++;
}
}
else if (i < s1)
{
//When first sub array element exists
auxiliary[front + counter] = first_subarray[i];
i++;
}
else
{
//When second sub array element exists
auxiliary[front + counter] = second_subarray[j];
j++;
}
counter++;
}
}
// Perform merge sort
// Handles the request of split and merge in array elements
public void mergeSort(int[] auxiliary, int front, int tail)
{
if (front < tail)
{
//Get middle location of given index
int middle = (front + tail) / 2;
//Split the array into two parts
mergeSort(auxiliary, front, middle);
mergeSort(auxiliary, middle + 1, tail);
//Combine split array into sorted way
mergeElements(auxiliary, front, tail, middle);
}
}
//
public void sortMatrix(int[][] matrix, int row, int col)
{
int size = row * col;
if (size <= 0)
{
return;
}
// This is collecting of matrix elements
int[] auxiliary = new int[size];
int i = 0;
int j = 0;
int k = 0;
// Collect elements of 2d array
for (i = 0; i < row; ++i)
{
for (j = 0; j < col; ++j)
{
auxiliary[k] = matrix[i][j];
k++;
}
}
mergeSort(auxiliary, 0, size - 1);
k = 0;
// Put sorted elements into matrix
for (i = 0; i < row; ++i)
{
for (j = 0; j < col; ++j)
{
matrix[i][j] = auxiliary[k];
k++;
}
}
}
public static void main(String[] args)
{
MyMatrix obj = new MyMatrix();
int [][]matrix =
{
{2, 6, 9 , 5 },
{13, 7, 16 , 15 },
{45, 14, 6, 82 },
{54, 55, 4, 18 },
{1, 6, 12, 19 },
{7, 51, 12, 3 },
{41, 19, 8, 50 }
};
int row = matrix.length;
int col = matrix[0].length;
// Before Sort matrix elements
System.out.print("\n Before sorted matrix\n");
obj.printMatrix(matrix,row,col);
// Sort matrix elements
obj.sortMatrix(matrix, row, col);
//After Sort matrix elements
System.out.print("\n After sorted matrix\n");
obj.printMatrix(matrix,row,col);
}
}
Output
Before sorted matrix
2 6 9 5
13 7 16 15
45 14 6 82
54 55 4 18
1 6 12 19
7 51 12 3
41 19 8 50
After sorted matrix
1 2 3 4
5 6 6 6
7 7 8 9
12 12 13 14
15 16 18 19
19 41 45 50
51 54 55 82
// Include header file
#include <iostream>
// Matrix size
#define R 7
#define C 4
using namespace std;
/*
C++ Program
Sort matrix elements
*/
class MyMatrix
{
public:
// Displaying of the matrix elements
void printMatrix(int matrix[R][C])
{
int i;
int j;
for (i = 0; i < R; ++i)
{
for (j = 0; j < C; ++j)
{
cout << " " << matrix[i][j];
}
cout << "\n";
}
cout << "\n";
}
// Sorted merge of given two subarrays of an array
void mergeElements(int auxiliary[], int front, int tail, int middle)
{
// Get the size of first subarray
int s1 = (middle - front) + 1;
// Get the size of second subarray
int s2 = tail - middle;
// Creating auxiliary storage to store elements
int first_subarray[s1];
int second_subarray[s2];
// Loop controlling variables
int i = 0;
int j = 0;
int counter = 0;
// Get the elements of first subarray
for (i = 0; i < s1; i++)
{
first_subarray[i] = auxiliary[front + i];
}
// Get the elements of second subarray
for (i = 0; i < s2; i++)
{
second_subarray[i] = auxiliary[middle + i + 1];
}
i = 0;
// Add sorted elements into actual array
while (counter < s1 + s2)
{
// Check that both sub array element exists or not
if (i < s1 && j < s2)
{
if (first_subarray[i] <= second_subarray[j])
{
// When first array [i] element are smaller
auxiliary[front + counter] = first_subarray[i];
i++;
}
else
{
// When second array [j] element are smaller
auxiliary[front + counter] = second_subarray[j];
j++;
}
}
else if (i < s1)
{
// When first sub array element exists
auxiliary[front + counter] = first_subarray[i];
i++;
}
else
{
// When second sub array element exists
auxiliary[front + counter] = second_subarray[j];
j++;
}
counter++;
}
}
// Perform merge sort
// Handles the request of split and merge in array elements
void mergeSort(int auxiliary[], int front, int tail)
{
if (front < tail)
{
// Get middle location of given index
int middle = (front + tail) / 2;
// Split the array into two parts
this->mergeSort(auxiliary, front, middle);
this->mergeSort(auxiliary, middle + 1, tail);
// Combine split array into sorted way
this->mergeElements(auxiliary, front, tail, middle);
}
}
//
void sortMatrix(int matrix[R][C])
{
int size = R * C;
if (size <= 0)
{
return;
}
// This is collecting of matrix elements
int auxiliary[size];
int i = 0;
int j = 0;
int k = 0;
// Collect elements of 2d array
for (i = 0; i < R; ++i)
{
for (j = 0; j < C; ++j)
{
auxiliary[k] = matrix[i][j];
k++;
}
}
this->mergeSort(auxiliary, 0, size - 1);
k = 0;
// Put sorted elements into matrix
for (i = 0; i < R; ++i)
{
for (j = 0; j < C; ++j)
{
matrix[i][j] = auxiliary[k];
k++;
}
}
}
};
int main()
{
MyMatrix obj = MyMatrix();
int matrix[R][C] =
{
{2, 6, 9 , 5 },
{13, 7, 16 , 15 },
{45, 14, 6, 82 },
{54, 55, 4, 18 },
{1, 6, 12, 19 },
{7, 51, 12, 3 },
{41, 19, 8, 50 }
};
// Before Sort matrix elements
cout << "\n Before sorted matrix\n";
obj.printMatrix(matrix);
// Sort matrix elements
obj.sortMatrix(matrix);
// After Sort matrix elements
cout << "\n After sorted matrix\n";
obj.printMatrix(matrix);
return 0;
}
Output
Before sorted matrix
2 6 9 5
13 7 16 15
45 14 6 82
54 55 4 18
1 6 12 19
7 51 12 3
41 19 8 50
After sorted matrix
1 2 3 4
5 6 6 6
7 7 8 9
12 12 13 14
15 16 18 19
19 41 45 50
51 54 55 82
// Include namespace system
using System;
/*
C# Program
Sort matrix elements
*/
public class MyMatrix
{
// Displaying of the matrix elements
public void printMatrix(int[,] matrix, int row, int col)
{
int i;
int j;
for (i = 0; i < row; ++i)
{
for (j = 0; j < col; ++j)
{
Console.Write(" " + matrix[i,j]);
}
Console.Write("\n");
}
Console.Write("\n");
}
// Sorted merge of given two subarrays of an array
public void mergeElements(int[] auxiliary, int front, int tail, int middle)
{
// Get the size of first subarray
int s1 = (middle - front) + 1;
// Get the size of second subarray
int s2 = tail - middle;
// Creating auxiliary storage to store elements
int[] first_subarray = new int[s1];
int[] second_subarray = new int[s2];
// Loop controlling variables
int i = 0;
int j = 0;
int counter = 0;
// Get the elements of first subarray
for (i = 0; i < s1; i++)
{
first_subarray[i] = auxiliary[front + i];
}
// Get the elements of second subarray
for (i = 0; i < s2; i++)
{
second_subarray[i] = auxiliary[middle + i + 1];
}
i = 0;
// Add sorted elements into actual array
while (counter < s1 + s2)
{
// Check that both sub array element exists or not
if (i < s1 && j < s2)
{
if (first_subarray[i] <= second_subarray[j])
{
// When first array [i] element are smaller
auxiliary[front + counter] = first_subarray[i];
i++;
}
else
{
// When second array [j] element are smaller
auxiliary[front + counter] = second_subarray[j];
j++;
}
}
else if (i < s1)
{
// When first sub array element exists
auxiliary[front + counter] = first_subarray[i];
i++;
}
else
{
// When second sub array element exists
auxiliary[front + counter] = second_subarray[j];
j++;
}
counter++;
}
}
// Perform merge sort
// Handles the request of split and merge in array elements
public void mergeSort(int[] auxiliary, int front, int tail)
{
if (front < tail)
{
// Get middle location of given index
int middle = (front + tail) / 2;
// Split the array into two parts
mergeSort(auxiliary, front, middle);
mergeSort(auxiliary, middle + 1, tail);
// Combine split array into sorted way
mergeElements(auxiliary, front, tail, middle);
}
}
//
public void sortMatrix(int[,] matrix, int row, int col)
{
int size = row * col;
if (size <= 0)
{
return;
}
// This is collecting of matrix elements
int[] auxiliary = new int[size];
int i = 0;
int j = 0;
int k = 0;
// Collect elements of 2d array
for (i = 0; i < row; ++i)
{
for (j = 0; j < col; ++j)
{
auxiliary[k] = matrix[i,j];
k++;
}
}
mergeSort(auxiliary, 0, size - 1);
k = 0;
// Put sorted elements into matrix
for (i = 0; i < row; ++i)
{
for (j = 0; j < col; ++j)
{
matrix[i,j] = auxiliary[k];
k++;
}
}
}
public static void Main(String[] args)
{
MyMatrix obj = new MyMatrix();
int[,] matrix =
{
{2, 6, 9 , 5 },
{13, 7, 16 , 15 },
{45, 14, 6, 82 },
{54, 55, 4, 18 },
{1, 6, 12, 19 },
{7, 51, 12, 3 },
{41, 19, 8, 50 }
};
int row = matrix.GetLength(0);
int col = matrix.GetLength(1);
// Before Sort matrix elements
Console.Write("\n Before sorted matrix\n");
obj.printMatrix(matrix, row, col);
// Sort matrix elements
obj.sortMatrix(matrix, row, col);
// After Sort matrix elements
Console.Write("\n After sorted matrix\n");
obj.printMatrix(matrix, row, col);
}
}
Output
Before sorted matrix
2 6 9 5
13 7 16 15
45 14 6 82
54 55 4 18
1 6 12 19
7 51 12 3
41 19 8 50
After sorted matrix
1 2 3 4
5 6 6 6
7 7 8 9
12 12 13 14
15 16 18 19
19 41 45 50
51 54 55 82
<?php
/*
Php Program
Sort matrix elements
*/
class MyMatrix
{
// Displaying of the matrix elements
public function printMatrix( & $matrix, $row, $col)
{
$i;
$j;
for ($i = 0; $i < $row; ++$i)
{
for ($j = 0; $j < $col; ++$j)
{
echo " ". $matrix[$i][$j];
}
echo "\n";
}
echo "\n";
}
// Sorted merge of given two subarrays of an array
public function mergeElements( & $auxiliary, $front, $tail, $middle)
{
// Get the size of first subarray
$s1 = ($middle - $front) + 1;
// Get the size of second subarray
$s2 = $tail - $middle;
// Creating auxiliary storage to store elements
$first_subarray = array_fill(0, $s1, 0);
$second_subarray = array_fill(0, $s2, 0);
// Loop controlling variables
$i = 0;
$j = 0;
$counter = 0;
// Get the elements of first subarray
for ($i = 0; $i < $s1; $i++)
{
$first_subarray[$i] = $auxiliary[$front + $i];
}
// Get the elements of second subarray
for ($i = 0; $i < $s2; $i++)
{
$second_subarray[$i] = $auxiliary[$middle + $i + 1];
}
$i = 0;
// Add sorted elements into actual array
while ($counter < $s1 + $s2)
{
// Check that both sub array element exists or not
if ($i < $s1 && $j < $s2)
{
if ($first_subarray[$i] <= $second_subarray[$j])
{
// When first array [i] element are smaller
$auxiliary[$front + $counter] = $first_subarray[$i];
$i++;
}
else
{
// When second array [j] element are smaller
$auxiliary[$front + $counter] = $second_subarray[$j];
$j++;
}
}
else if ($i < $s1)
{
// When first sub array element exists
$auxiliary[$front + $counter] = $first_subarray[$i];
$i++;
}
else
{
// When second sub array element exists
$auxiliary[$front + $counter] = $second_subarray[$j];
$j++;
}
$counter++;
}
}
// Perform merge sort
// Handles the request of split and merge in array elements
public function mergeSort( & $auxiliary, $front, $tail)
{
if ($front < $tail)
{
// Get middle location of given index
$middle = intval(($front + $tail) / 2);
// Split the array into two parts
$this->mergeSort($auxiliary, $front, $middle);
$this->mergeSort($auxiliary, $middle + 1, $tail);
// Combine split array into sorted way
$this->mergeElements($auxiliary, $front, $tail, $middle);
}
}
//
public function sortMatrix( & $matrix, $row, $col)
{
$size = $row * $col;
if ($size <= 0)
{
return;
}
// This is collecting of matrix elements
$auxiliary = array_fill(0, $size, 0);
$i = 0;
$j = 0;
$k = 0;
// Collect elements of 2d array
for ($i = 0; $i < $row; ++$i)
{
for ($j = 0; $j < $col; ++$j)
{
$auxiliary[$k] = $matrix[$i][$j];
$k++;
}
}
$this->mergeSort($auxiliary, 0, $size - 1);
$k = 0;
// Put sorted elements into matrix
for ($i = 0; $i < $row; ++$i)
{
for ($j = 0; $j < $col; ++$j)
{
$matrix[$i][$j] = $auxiliary[$k];
$k++;
}
}
}
}
function main()
{
$obj = new MyMatrix();
$matrix = array(
array(2, 6, 9, 5),
array(13, 7, 16, 15),
array(45, 14, 6, 82),
array(54, 55, 4, 18),
array(1, 6, 12, 19),
array(7, 51, 12, 3),
array(41, 19, 8, 50)
);
$row = count($matrix);
$col = count($matrix[0]);
// Before Sort matrix elements
echo "\n Before sorted matrix\n";
$obj->printMatrix($matrix, $row, $col);
// Sort matrix elements
$obj->sortMatrix($matrix, $row, $col);
// After Sort matrix elements
echo "\n After sorted matrix\n";
$obj->printMatrix($matrix, $row, $col);
}
main();
Output
Before sorted matrix
2 6 9 5
13 7 16 15
45 14 6 82
54 55 4 18
1 6 12 19
7 51 12 3
41 19 8 50
After sorted matrix
1 2 3 4
5 6 6 6
7 7 8 9
12 12 13 14
15 16 18 19
19 41 45 50
51 54 55 82
/*
Node Js Program
Sort matrix elements
*/
class MyMatrix
{
// Displaying of the matrix elements
printMatrix(matrix, row, col)
{
var i;
var j;
for (i = 0; i < row; ++i)
{
for (j = 0; j < col; ++j)
{
process.stdout.write(" " + matrix[i][j]);
}
process.stdout.write("\n");
}
process.stdout.write("\n");
}
// Sorted merge of given two subarrays of an array
mergeElements(auxiliary, front, tail, middle)
{
// Get the size of first subarray
var s1 = (middle - front) + 1;
// Get the size of second subarray
var s2 = tail - middle;
// Creating auxiliary storage to store elements
var first_subarray = Array(s1).fill(0);
var second_subarray = Array(s2).fill(0);
// Loop controlling variables
var i = 0;
var j = 0;
var counter = 0;
// Get the elements of first subarray
for (i = 0; i < s1; i++)
{
first_subarray[i] = auxiliary[front + i];
}
// Get the elements of second subarray
for (i = 0; i < s2; i++)
{
second_subarray[i] = auxiliary[middle + i + 1];
}
i = 0;
// Add sorted elements into actual array
while (counter < s1 + s2)
{
// Check that both sub array element exists or not
if (i < s1 && j < s2)
{
if (first_subarray[i] <= second_subarray[j])
{
// When first array [i] element are smaller
auxiliary[front + counter] = first_subarray[i];
i++;
}
else
{
// When second array [j] element are smaller
auxiliary[front + counter] = second_subarray[j];
j++;
}
}
else if (i < s1)
{
// When first sub array element exists
auxiliary[front + counter] = first_subarray[i];
i++;
}
else
{
// When second sub array element exists
auxiliary[front + counter] = second_subarray[j];
j++;
}
counter++;
}
}
// Perform merge sort
// Handles the request of split and merge in array elements
mergeSort(auxiliary, front, tail)
{
if (front < tail)
{
// Get middle location of given index
var middle = parseInt((front + tail) / 2);
// Split the array into two parts
this.mergeSort(auxiliary, front, middle);
this.mergeSort(auxiliary, middle + 1, tail);
// Combine split array into sorted way
this.mergeElements(auxiliary, front, tail, middle);
}
}
//
sortMatrix(matrix, row, col)
{
var size = row * col;
if (size <= 0)
{
return;
}
// This is collecting of matrix elements
var auxiliary = Array(size).fill(0);
var i = 0;
var j = 0;
var k = 0;
// Collect elements of 2d array
for (i = 0; i < row; ++i)
{
for (j = 0; j < col; ++j)
{
auxiliary[k] = matrix[i][j];
k++;
}
}
this.mergeSort(auxiliary, 0, size - 1);
k = 0;
// Put sorted elements into matrix
for (i = 0; i < row; ++i)
{
for (j = 0; j < col; ++j)
{
matrix[i][j] = auxiliary[k];
k++;
}
}
}
}
function main()
{
var obj = new MyMatrix();
var matrix = [
[2, 6, 9, 5] ,
[13, 7, 16, 15] ,
[45, 14, 6, 82] ,
[54, 55, 4, 18] ,
[1, 6, 12, 19] ,
[7, 51, 12, 3] ,
[41, 19, 8, 50]
];
var row = matrix.length;
var col = matrix[0].length;
// Before Sort matrix elements
process.stdout.write("\n Before sorted matrix\n");
obj.printMatrix(matrix, row, col);
// Sort matrix elements
obj.sortMatrix(matrix, row, col);
// After Sort matrix elements
process.stdout.write("\n After sorted matrix\n");
obj.printMatrix(matrix, row, col);
}
main();
Output
Before sorted matrix
2 6 9 5
13 7 16 15
45 14 6 82
54 55 4 18
1 6 12 19
7 51 12 3
41 19 8 50
After sorted matrix
1 2 3 4
5 6 6 6
7 7 8 9
12 12 13 14
15 16 18 19
19 41 45 50
51 54 55 82
# Python 3 Program
# Sort matrix elements
class MyMatrix :
# Displaying of the matrix elements
def printMatrix(self, matrix, row, col) :
i = 0
j = 0
while (i < row) :
j = 0
while (j < col) :
print(" ", matrix[i][j], end = "")
j += 1
print(end = "\n")
i += 1
print("\n", end = "")
# Sorted merge of given two subarrays of an array
def mergeElements(self, auxiliary, front, tail, middle) :
# Get the size of first subarray
s1 = (middle - front) + 1
# Get the size of second subarray
s2 = tail - middle
# Creating auxiliary storage to store elements
first_subarray = [0] * (s1)
second_subarray = [0] * (s2)
# Loop controlling variables
i = 0
j = 0
counter = 0
# Get the elements of first subarray
while (i < s1) :
first_subarray[i] = auxiliary[front + i]
i += 1
# Get the elements of second subarray
i = 0
while (i < s2) :
second_subarray[i] = auxiliary[middle + i + 1]
i += 1
i = 0
# Add sorted elements into actual array
while (counter < s1 + s2) :
# Check that both sub array element exists or not
if (i < s1 and j < s2) :
if (first_subarray[i] <= second_subarray[j]) :
# When first array [i] element are smaller
auxiliary[front + counter] = first_subarray[i]
i += 1
else :
# When second array [j] element are smaller
auxiliary[front + counter] = second_subarray[j]
j += 1
elif(i < s1) :
# When first sub array element exists
auxiliary[front + counter] = first_subarray[i]
i += 1
else :
# When second sub array element exists
auxiliary[front + counter] = second_subarray[j]
j += 1
counter += 1
# Perform merge sort
# Handles the request of split and merge in array elements
def mergeSort(self, auxiliary, front, tail) :
if (front < tail) :
# Get middle location of given index
middle = int((front + tail) / 2)
# Split the array into two parts
self.mergeSort(auxiliary, front, middle)
self.mergeSort(auxiliary, middle + 1, tail)
# Combine split array into sorted way
self.mergeElements(auxiliary, front, tail, middle)
#
def sortMatrix(self, matrix, row, col) :
size = row * col
if (size <= 0) :
return
# This is collecting of matrix elements
auxiliary = [0] * (size)
i = 0
j = 0
k = 0
# Collect elements of 2d array
while (i < row) :
j = 0
while (j < col) :
auxiliary[k] = matrix[i][j]
k += 1
j += 1
i += 1
self.mergeSort(auxiliary, 0, size - 1)
k = 0
# Put sorted elements into matrix
i = 0
while (i < row) :
j = 0
while (j < col) :
matrix[i][j] = auxiliary[k]
k += 1
j += 1
i += 1
def main() :
obj = MyMatrix()
matrix = [
[2, 6, 9, 5] ,
[13, 7, 16, 15] ,
[45, 14, 6, 82] ,
[54, 55, 4, 18] ,
[1, 6, 12, 19] ,
[7, 51, 12, 3] ,
[41, 19, 8, 50]
]
row = len(matrix)
col = len(matrix[0])
# Before Sort matrix elements
print("\n Before sorted matrix")
obj.printMatrix(matrix, row, col)
# Sort matrix elements
obj.sortMatrix(matrix, row, col)
# After Sort matrix elements
print("\n After sorted matrix")
obj.printMatrix(matrix, row, col)
if __name__ == "__main__": main()
Output
Before sorted matrix
2 6 9 5
13 7 16 15
45 14 6 82
54 55 4 18
1 6 12 19
7 51 12 3
41 19 8 50
After sorted matrix
1 2 3 4
5 6 6 6
7 7 8 9
12 12 13 14
15 16 18 19
19 41 45 50
51 54 55 82
# Ruby Program
# Sort matrix elements
class MyMatrix
# Displaying of the matrix elements
def printMatrix(matrix, row, col)
i = 0
j = 0
while (i < row)
j = 0
while (j < col)
print(" ", matrix[i][j])
j += 1
end
print("\n")
i += 1
end
print("\n")
end
# Sorted merge of given two subarrays of an array
def mergeElements(auxiliary, front, tail, middle)
# Get the size of first subarray
s1 = (middle - front) + 1
# Get the size of second subarray
s2 = tail - middle
# Creating auxiliary storage to store elements
first_subarray = Array.new(s1) {0}
second_subarray = Array.new(s2) {0}
# Loop controlling variables
i = 0
j = 0
counter = 0
# Get the elements of first subarray
while (i < s1)
first_subarray[i] = auxiliary[front + i]
i += 1
end
# Get the elements of second subarray
i = 0
while (i < s2)
second_subarray[i] = auxiliary[middle + i + 1]
i += 1
end
i = 0
# Add sorted elements into actual array
while (counter < s1 + s2)
# Check that both sub array element exists or not
if (i < s1 && j < s2)
if (first_subarray[i] <= second_subarray[j])
# When first array [i] element are smaller
auxiliary[front + counter] = first_subarray[i]
i += 1
else
# When second array [j] element are smaller
auxiliary[front + counter] = second_subarray[j]
j += 1
end
elsif(i < s1)
# When first sub array element exists
auxiliary[front + counter] = first_subarray[i]
i += 1
else
# When second sub array element exists
auxiliary[front + counter] = second_subarray[j]
j += 1
end
counter += 1
end
end
# Perform merge sort
# Handles the request of split and merge in array elements
def mergeSort(auxiliary, front, tail)
if (front < tail)
# Get middle location of given index
middle = (front + tail) / 2
# Split the array into two parts
self.mergeSort(auxiliary, front, middle)
self.mergeSort(auxiliary, middle + 1, tail)
# Combine split array into sorted way
self.mergeElements(auxiliary, front, tail, middle)
end
end
#
def sortMatrix(matrix, row, col)
size = row * col
if (size <= 0)
return
end
# This is collecting of matrix elements
auxiliary = Array.new(size) {0}
i = 0
j = 0
k = 0
# Collect elements of 2d array
while (i < row)
j = 0
while (j < col)
auxiliary[k] = matrix[i][j]
k += 1
j += 1
end
i += 1
end
self.mergeSort(auxiliary, 0, size - 1)
k = 0
# Put sorted elements into matrix
i = 0
while (i < row)
j = 0
while (j < col)
matrix[i][j] = auxiliary[k]
k += 1
j += 1
end
i += 1
end
end
end
def main()
obj = MyMatrix.new()
matrix = [
[2, 6, 9, 5] ,
[13, 7, 16, 15] ,
[45, 14, 6, 82] ,
[54, 55, 4, 18] ,
[1, 6, 12, 19] ,
[7, 51, 12, 3] ,
[41, 19, 8, 50]
]
row = matrix.length
col = matrix[0].length
# Before Sort matrix elements
print("\n Before sorted matrix\n")
obj.printMatrix(matrix, row, col)
# Sort matrix elements
obj.sortMatrix(matrix, row, col)
# After Sort matrix elements
print("\n After sorted matrix\n")
obj.printMatrix(matrix, row, col)
end
main()
Output
Before sorted matrix
2 6 9 5
13 7 16 15
45 14 6 82
54 55 4 18
1 6 12 19
7 51 12 3
41 19 8 50
After sorted matrix
1 2 3 4
5 6 6 6
7 7 8 9
12 12 13 14
15 16 18 19
19 41 45 50
51 54 55 82
/*
Scala Program
Sort matrix elements
*/
class MyMatrix
{
// Displaying of the matrix elements
def printMatrix(matrix: Array[Array[Int]], row: Int, col: Int): Unit = {
var i: Int = 0;
var j: Int = 0;
while (i < row)
{
j = 0;
while (j < col)
{
print(" " + matrix(i)(j));
j += 1;
}
print("\n");
i += 1;
}
print("\n");
}
// Sorted merge of given two subarrays of an array
def mergeElements(auxiliary: Array[Int], front: Int, tail: Int, middle: Int): Unit = {
// Get the size of first subarray
var s1: Int = (middle - front) + 1;
// Get the size of second subarray
var s2: Int = tail - middle;
// Creating auxiliary storage to store elements
var first_subarray: Array[Int] = Array.fill[Int](s1)(0);
var second_subarray: Array[Int] = Array.fill[Int](s2)(0);
// Loop controlling variables
var i: Int = 0;
var j: Int = 0;
var counter: Int = 0;
// Get the elements of first subarray
while (i < s1)
{
first_subarray(i) = auxiliary(front + i);
i += 1;
}
// Get the elements of second subarray
i = 0;
while (i < s2)
{
second_subarray(i) = auxiliary(middle + i + 1);
i += 1;
}
i = 0;
// Add sorted elements into actual array
while (counter < s1 + s2)
{
// Check that both sub array element exists or not
if (i < s1 && j < s2)
{
if (first_subarray(i) <= second_subarray(j))
{
// When first array [i] element are smaller
auxiliary(front + counter) = first_subarray(i);
i += 1;
}
else
{
// When second array [j] element are smaller
auxiliary(front + counter) = second_subarray(j);
j += 1;
}
}
else if (i < s1)
{
// When first sub array element exists
auxiliary(front + counter) = first_subarray(i);
i += 1;
}
else
{
// When second sub array element exists
auxiliary(front + counter) = second_subarray(j);
j += 1;
}
counter += 1;
}
}
// Perform merge sort
// Handles the request of split and merge in array elements
def mergeSort(auxiliary: Array[Int], front: Int, tail: Int): Unit = {
if (front < tail)
{
// Get middle location of given index
var middle: Int = ((front + tail) / 2).toInt;
// Split the array into two parts
this.mergeSort(auxiliary, front, middle);
this.mergeSort(auxiliary, middle + 1, tail);
// Combine split array into sorted way
this.mergeElements(auxiliary, front, tail, middle);
}
}
//
def sortMatrix(matrix: Array[Array[Int]], row: Int, col: Int): Unit = {
var size: Int = row * col;
if (size <= 0)
{
return;
}
// This is collecting of matrix elements
var auxiliary: Array[Int] = Array.fill[Int](size)(0);
var i: Int = 0;
var j: Int = 0;
var k: Int = 0;
// Collect elements of 2d array
while (i < row)
{
j = 0;
while (j < col)
{
auxiliary(k) = matrix(i)(j);
k += 1;
j += 1;
}
i += 1;
}
this.mergeSort(auxiliary, 0, size - 1);
k = 0;
// Put sorted elements into matrix
i = 0;
while (i < row)
{
j = 0;
while (j < col)
{
matrix(i)(j) = auxiliary(k);
k += 1;
j += 1;
}
i += 1;
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var obj: MyMatrix = new MyMatrix();
var matrix: Array[Array[Int]] = Array(
Array(2, 6, 9, 5),
Array(13, 7, 16, 15),
Array(45, 14, 6, 82),
Array(54, 55, 4, 18),
Array(1, 6, 12, 19),
Array(7, 51, 12, 3),
Array(41, 19, 8, 50)
);
var row: Int = matrix.length;
var col: Int = matrix(0).length;
// Before Sort matrix elements
print("\n Before sorted matrix\n");
obj.printMatrix(matrix, row, col);
// Sort matrix elements
obj.sortMatrix(matrix, row, col);
// After Sort matrix elements
print("\n After sorted matrix\n");
obj.printMatrix(matrix, row, col);
}
}
Output
Before sorted matrix
2 6 9 5
13 7 16 15
45 14 6 82
54 55 4 18
1 6 12 19
7 51 12 3
41 19 8 50
After sorted matrix
1 2 3 4
5 6 6 6
7 7 8 9
12 12 13 14
15 16 18 19
19 41 45 50
51 54 55 82
/*
Swift 4 Program
Sort matrix elements
*/
class MyMatrix
{
// Displaying of the matrix elements
func printMatrix(_ matrix: [[Int]], _ row: Int, _ col: Int)
{
var i: Int = 0;
var j: Int = 0;
while (i < row)
{
j = 0;
while (j < col)
{
print(" ", matrix[i][j], terminator: "");
j += 1;
}
print("\n", terminator: "");
i += 1;
}
print("\n", terminator: "");
}
// Sorted merge of given two subarrays of an array
func mergeElements(_ auxiliary: inout[Int], _ front: Int, _ tail: Int, _ middle: Int)
{
// Get the size of first subarray
let s1: Int = (middle - front) + 1;
// Get the size of second subarray
let s2: Int = tail - middle;
// Creating auxiliary storage to store elements
var first_subarray: [Int] = Array(repeating: 0, count: s1);
var second_subarray: [Int] = Array(repeating: 0, count: s2);
// Loop controlling variables
var i: Int = 0;
var j: Int = 0;
var counter: Int = 0;
// Get the elements of first subarray
while (i < s1)
{
first_subarray[i] = auxiliary[front + i];
i += 1;
}
// Get the elements of second subarray
i = 0;
while (i < s2)
{
second_subarray[i] = auxiliary[middle + i + 1];
i += 1;
}
i = 0;
// Add sorted elements into actual array
while (counter < s1 + s2)
{
// Check that both sub array element exists or not
if (i < s1 && j < s2)
{
if (first_subarray[i] <= second_subarray[j])
{
// When first array [i] element are smaller
auxiliary[front + counter] = first_subarray[i];
i += 1;
}
else
{
// When second array [j] element are smaller
auxiliary[front + counter] = second_subarray[j];
j += 1;
}
}
else if (i < s1)
{
// When first sub array element exists
auxiliary[front + counter] = first_subarray[i];
i += 1;
}
else
{
// When second sub array element exists
auxiliary[front + counter] = second_subarray[j];
j += 1;
}
counter += 1;
}
}
// Perform merge sort
// Handles the request of split and merge in array elements
func mergeSort(_ auxiliary: inout[Int], _ front: Int, _ tail: Int)
{
if (front < tail)
{
// Get middle location of given index
let middle: Int = (front + tail) / 2;
// Split the array into two parts
self.mergeSort(&auxiliary, front, middle);
self.mergeSort(&auxiliary, middle + 1, tail);
// Combine split array into sorted way
self.mergeElements(&auxiliary, front, tail, middle);
}
}
//
func sortMatrix(_ matrix: inout[[Int]], _ row: Int, _ col: Int)
{
let size: Int = row * col;
if (size <= 0)
{
return;
}
// This is collecting of matrix elements
var auxiliary: [Int] = Array(repeating: 0, count: size);
var i: Int = 0;
var j: Int = 0;
var k: Int = 0;
// Collect elements of 2d array
while (i < row)
{
j = 0;
while (j < col)
{
auxiliary[k] = matrix[i][j];
k += 1;
j += 1;
}
i += 1;
}
self.mergeSort(&auxiliary, 0, size - 1);
k = 0;
// Put sorted elements into matrix
i = 0;
while (i < row)
{
j = 0;
while (j < col)
{
matrix[i][j] = auxiliary[k];
k += 1;
j += 1;
}
i += 1;
}
}
}
func main()
{
let obj: MyMatrix = MyMatrix();
var matrix: [[Int]] = [
[2, 6, 9, 5] ,
[13, 7, 16, 15] ,
[45, 14, 6, 82] ,
[54, 55, 4, 18] ,
[1, 6, 12, 19] ,
[7, 51, 12, 3] ,
[41, 19, 8, 50]
];
let row: Int = matrix.count;
let col: Int = matrix[0].count;
// Before Sort matrix elements
print("\n Before sorted matrix\n", terminator: "");
obj.printMatrix(matrix, row, col);
// Sort matrix elements
obj.sortMatrix(&matrix, row, col);
// After Sort matrix elements
print("\n After sorted matrix\n", terminator: "");
obj.printMatrix(matrix, row, col);
}
main();
Output
Before sorted matrix
2 6 9 5
13 7 16 15
45 14 6 82
54 55 4 18
1 6 12 19
7 51 12 3
41 19 8 50
After sorted matrix
1 2 3 4
5 6 6 6
7 7 8 9
12 12 13 14
15 16 18 19
19 41 45 50
51 54 55 82
/*
Kotlin Program
Sort matrix elements
*/
class MyMatrix
{
// Displaying of the matrix elements
fun printMatrix(matrix: Array <Array<Int>> , row: Int, col: Int): Unit
{
var i: Int = 0;
var j: Int ;
while (i < row)
{
j = 0;
while (j < col)
{
print(" " + matrix[i][j]);
j += 1;
}
print("\n");
i += 1;
}
print("\n");
}
// Sorted merge of given two subarrays of an array
fun mergeElements(auxiliary: Array<Int> , front: Int, tail: Int, middle: Int): Unit
{
// Get the size of first subarray
var s1: Int = (middle - front) + 1;
// Get the size of second subarray
var s2: Int = tail - middle;
// Creating auxiliary storage to store elements
var first_subarray: Array <Int> = Array(s1){0};
var second_subarray: Array < Int > = Array(s2){0};
// Loop controlling variables
var i: Int = 0;
var j: Int = 0;
var counter: Int = 0;
// Get the elements of first subarray
while (i < s1)
{
first_subarray[i] = auxiliary[front + i];
i += 1;
}
// Get the elements of second subarray
i = 0;
while (i < s2)
{
second_subarray[i] = auxiliary[middle + i + 1];
i += 1;
}
i = 0;
// Add sorted elements into actual array
while (counter < s1 + s2)
{
// Check that both sub array element exists or not
if (i < s1 && j < s2)
{
if (first_subarray[i] <= second_subarray[j])
{
// When first array [i] element are smaller
auxiliary[front + counter] = first_subarray[i];
i += 1;
}
else
{
// When second array [j] element are smaller
auxiliary[front + counter] = second_subarray[j];
j += 1;
}
}
else
if (i < s1)
{
// When first sub array element exists
auxiliary[front + counter] = first_subarray[i];
i += 1;
}
else
{
// When second sub array element exists
auxiliary[front + counter] = second_subarray[j];
j += 1;
}
counter += 1;
}
}
// Perform merge sort
// Handles the request of split and merge in array elements
fun mergeSort(auxiliary: Array < Int > , front: Int, tail: Int): Unit
{
if (front < tail)
{
// Get middle location of given index
var middle: Int = (front + tail) / 2;
// Split the array into two parts
this.mergeSort(auxiliary, front, middle);
this.mergeSort(auxiliary, middle + 1, tail);
// Combine split array into sorted way
this.mergeElements(auxiliary, front, tail, middle);
}
}
//
fun sortMatrix(matrix: Array < Array < Int >> , row: Int, col: Int): Unit
{
var size: Int = row * col;
if (size <= 0)
{
return;
}
// This is collecting of matrix elements
var auxiliary: Array < Int > = Array(size){0};
var i: Int = 0;
var j: Int ;
var k: Int = 0;
// Collect elements of 2d array
while (i < row)
{
j = 0;
while (j < col)
{
auxiliary[k] = matrix[i][j];
k += 1;
j += 1;
}
i += 1;
}
this.mergeSort(auxiliary, 0, size - 1);
k = 0;
// Put sorted elements into matrix
i = 0;
while (i < row)
{
j = 0;
while (j < col)
{
matrix[i][j] = auxiliary[k];
k += 1;
j += 1;
}
i += 1;
}
}
}
fun main(args: Array < String > ): Unit
{
var obj: MyMatrix = MyMatrix();
var matrix: Array<Array<Int>> = arrayOf(
arrayOf(2, 6, 9, 5),
arrayOf(13, 7, 16, 15),
arrayOf(45, 14, 6, 82),
arrayOf(54, 55, 4, 18),
arrayOf(1, 6, 12, 19),
arrayOf(7, 51, 12, 3),
arrayOf(41, 19, 8, 50)
);
var row: Int = matrix.count();
var col: Int = matrix[0].count();
// Before Sort matrix elements
print("\n Before sorted matrix\n");
obj.printMatrix(matrix, row, col);
// Sort matrix elements
obj.sortMatrix(matrix, row, col);
// After Sort matrix elements
print("\n After sorted matrix\n");
obj.printMatrix(matrix, row, col);
}
Output
Before sorted matrix
2 6 9 5
13 7 16 15
45 14 6 82
54 55 4 18
1 6 12 19
7 51 12 3
41 19 8 50
After sorted matrix
1 2 3 4
5 6 6 6
7 7 8 9
12 12 13 14
15 16 18 19
19 41 45 50
51 54 55 82
Output Explanation
The given Java code implements the above algorithm to sort the matrix elements. It prints the original matrix and the sorted matrix.
Time Complexity
The time complexity of the provided solution is O(row * col * log(row * col)), where 'row' is the number of rows and 'col' is the number of columns in the 2D matrix. The function collects all the elements of the matrix into the auxiliary array in O(row * col) time. Then, the merge sort algorithm is applied to the auxiliary array, which has a time complexity of O(row * col * log(row * col)). Finally, the elements from the sorted auxiliary array are updated back into the matrix in O(row * col) time. Therefore, the overall time complexity is dominated by the sorting step.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment