Convert given Matrix into sorted Spiral Matrix
The problem is to convert a given 2D matrix into a sorted spiral matrix. In a sorted spiral matrix, the elements are arranged in a spiral pattern starting from the top-left corner and moving in a clockwise direction.
Example
Consider the following 2D matrix:
4 6 2 2
3 7 6 5
1 5 6 6
5 5 4 8
1 5 12 9
7 5 2 3
1 9 8 10
The sorted spiral matrix will be:
1 1 1 2
6 6 6 2
6 12 7 2
5 10 7 3
5 9 8 3
5 9 8 4
5 5 5 4
Idea to Solve the Problem
To convert the given matrix into a sorted spiral matrix, 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 in ascending order.
- Traverse the matrix in a spiral pattern from the top-left corner to the bottom-right corner and replace each element with the corresponding element from the sorted auxiliary array.
Algorithm
- Create a function
print_matrix
to display the elements of the matrix. - Create a function
merge_elements
to merge two sorted subarrays of the auxiliary array. - Create a function
sort_element
to perform a merge sort on the auxiliary array. - Create a function
update_element
to update the matrix with elements from the sorted auxiliary array in a spiral pattern. - Create a function
sorted_spiral
to convert the given matrix into a sorted spiral matrix. - In the
main
function, define the 2D matrix and its dimensions. - Display the original matrix.
- Call the
sorted_spiral
function to convert the matrix into a sorted spiral matrix. - Display the sorted spiral matrix.
Pseudocode
sorted_spiral(row, col, matrix):
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
sort_element(auxiliary, 0, size - 1)
update_element(row, col, matrix, auxiliary, 0, 0, row - 1, col - 1, size)
update_element(row, col, matrix, auxiliary, s_row, s_col, e_row, e_col, size):
// Left to right
for i from s_col to e_col and size > 0:
matrix[s_row][i] = auxiliary[row * col - size]
size = size - 1
// Top to down
for i from s_row + 1 to e_row and size > 0:
matrix[i][e_col] = auxiliary[row * col - size]
size = size - 1
// Bottom right to bottom left
for i from e_col - 1 to s_col and size > 0:
matrix[e_row][i] = auxiliary[row * col - size]
size = size - 1
// Bottom left to top
for i from e_row - 1 to s_row and size > 0:
matrix[i][s_col] = auxiliary[row * col - size]
size = size - 1
if s_row + 1 <= e_row - 1 and size > 0:
// Recursive call
update_element(row, col, matrix, auxiliary, s_row + 1, s_col + 1, e_row - 1, e_col - 1, size)
// The remaining functions (print_matrix, merge_elements, sort_element) are also provided in the Java code.
Code Solution
// C Program
// Convert given Matrix into sorted Spiral Matrix
#include <stdio.h>
#define R 7
#define C 4
//Displaying of the matrix elements
void print_matrix(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 merge_elements(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++;
}
}
//Split the array elements into two parts
void sort_element(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
sort_element(auxiliary, front, middle);
sort_element(auxiliary, middle + 1, tail);
//Combine split array into sorted way
merge_elements(auxiliary, front, tail, middle);
}
}
void update_element(int matrix[R][C], int auxiliary[], int s_row, int s_col, int e_row, int e_col, int size)
{
//Left to right
for (int i = s_col; i <= e_col && size > 0; ++i)
{
matrix[s_row][i] = auxiliary[R *C - size];
size--;
}
//Top to down
for (int i = s_row + 1; i <= e_row && size > 0; ++i)
{
matrix[i][e_col] = auxiliary[R *C - size];
size--;
}
//Bottom right to bottom-left
for (int i = e_col - 1; i >= s_col && size > 0; --i)
{
matrix[e_row][i] = auxiliary[R *C - size];
size--;
}
//Bottom left to top
for (int i = e_row - 1; i > s_row && size > 0; --i)
{
matrix[i][s_row] = auxiliary[R *C - size];
size--;
}
if (s_row + 1 <= e_row - 1 && size > 0)
{
//Recursive call
update_element(matrix, auxiliary, s_row + 1, s_col + 1, e_row - 1, e_col - 1, size);
}
}
void sorted_spiral(int matrix[R][C])
{
int size = R *C;
if (size <= 0)
{
return;
}
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++;
}
}
sort_element(auxiliary, 0, size - 1);
update_element(matrix, auxiliary, 0, 0, R - 1, C - 1, size);
}
int main()
{
int matrix[R][C] =
{
{4, 6, 2 , 2 },
{3, 7, 6 , 5 },
{1, 5, 6, 6 },
{5, 5, 4, 8 },
{1, 5, 12, 9 },
{7, 5, 2, 3 },
{1, 9, 8, 10 }
};
printf("\n Before sorted spiral\n");
print_matrix(matrix);
sorted_spiral(matrix);
printf("\n After sorted spiral\n");
print_matrix(matrix);
return 0;
}
Output
Before sorted spiral
4 6 2 2
3 7 6 5
1 5 6 6
5 5 4 8
1 5 12 9
7 5 2 3
1 9 8 10
After sorted spiral
1 1 1 2
6 6 6 2
6 12 7 2
5 10 7 3
5 9 8 3
5 9 8 4
5 5 5 4
/*
Java program
Convert given Matrix into sorted Spiral Matrix
*/
// Define TreeNode
class MyMatrix
{
//Displaying of the matrix elements
public void print_matrix(int row, int col, int[][] matrix)
{
for (int i = 0; i < row; ++i)
{
for (int 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 merge_elements(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++;
}
}
//Split the array elements into two parts
public void sort_element(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
sort_element(auxiliary, front, middle);
sort_element(auxiliary, middle + 1, tail);
//Combine split array into sorted way
merge_elements(auxiliary, front, tail, middle);
}
}
public void update_element(int row, int col, int[][] matrix, int[] auxiliary, int s_row, int s_col, int e_row, int e_col, int size)
{
//Left to right
for (int i = s_col; i <= e_col && size > 0; ++i)
{
matrix[s_row][i] = auxiliary[row * col - size];
size--;
}
//Top to down
for (int i = s_row + 1; i <= e_row && size > 0; ++i)
{
matrix[i][e_col] = auxiliary[row * col - size];
size--;
}
//Bottom right to bottom-left
for (int i = e_col - 1; i >= s_col && size > 0; --i)
{
matrix[e_row][i] = auxiliary[row * col - size];
size--;
}
//Bottom left to top
for (int i = e_row - 1; i > s_row && size > 0; --i)
{
matrix[i][s_row] = auxiliary[row * col - size];
size--;
}
if (s_row + 1 <= e_row - 1 && size > 0)
{
//Recursive call
update_element(row, col, matrix, auxiliary, s_row + 1, s_col + 1, e_row - 1, e_col - 1, size);
}
}
public void sorted_spiral(int row, int col, int[][] matrix)
{
int size = row * col;
if (size <= 0)
{
return;
}
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++;
}
}
sort_element(auxiliary, 0, size - 1);
update_element(row, col, matrix, auxiliary, 0, 0, row - 1, col - 1, size);
}
public static void main(String[] args)
{
MyMatrix obj = new MyMatrix();
// Define matrix of integer elements
int[][] matrix ={
{4, 6, 2 , 2 },
{3, 7, 6 , 5 },
{1, 5, 6, 6 },
{5, 5, 4, 8 },
{1, 5, 12, 9 },
{7, 5, 2, 3 },
{1, 9, 8, 10 }
};
int row = matrix.length;
int col = matrix[0].length;
System.out.print("\n Before sorted spiral\n");
obj.print_matrix(row, col, matrix);
obj.sorted_spiral(row, col, matrix);
System.out.print("\n After sorted spiral\n");
obj.print_matrix(row, col, matrix);
}
}
Output
Before sorted spiral
4 6 2 2
3 7 6 5
1 5 6 6
5 5 4 8
1 5 12 9
7 5 2 3
1 9 8 10
After sorted spiral
1 1 1 2
6 6 6 2
6 12 7 2
5 10 7 3
5 9 8 3
5 9 8 4
5 5 5 4
// Include header file
#include <iostream>
#define R 7
#define C 4
using namespace std;
/*
C++ program
Convert given Matrix into sorted Spiral Matrix
*/
// Define TreeNode
class MyMatrix
{
public:
// Displaying of the matrix elements
void print_matrix(int matrix[R][C] )
{
for (int i = 0; i < R; ++i)
{
for (int j = 0; j < C; ++j)
{
cout << " " << matrix[i][j];
}
cout << "\n";
}
cout << "\n";
}
// Sorted merge of given two subarrays of an array
void merge_elements(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++;
}
}
// Split the array elements into two parts
void sort_element(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->sort_element(auxiliary, front, middle);
this->sort_element(auxiliary, middle + 1, tail);
// Combine split array into sorted way
this->merge_elements(auxiliary, front, tail, middle);
}
}
void update_element(int matrix[R][C], int auxiliary[], int s_row, int s_col, int e_row, int e_col, int size)
{
// Left to right
for (int i = s_col; i <= e_col && size > 0; ++i)
{
matrix[s_row][i] = auxiliary[R * C - size];
size--;
}
// Top to down
for (int i = s_row + 1; i <= e_row && size > 0; ++i)
{
matrix[i][e_col] = auxiliary[R * C - size];
size--;
}
// Bottom right to bottom-left
for (int i = e_col - 1; i >= s_col && size > 0; --i)
{
matrix[e_row][i] = auxiliary[R * C - size];
size--;
}
// Bottom left to top
for (int i = e_row - 1; i > s_row && size > 0; --i)
{
matrix[i][s_row] = auxiliary[R * C - size];
size--;
}
if (s_row + 1 <= e_row - 1 && size > 0)
{
// Recursive call
this->update_element( matrix, auxiliary, s_row + 1, s_col + 1, e_row - 1, e_col - 1, size);
}
}
void sorted_spiral(int matrix[R][C])
{
int size = R * C;
if (size <= 0)
{
return;
}
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->sort_element(auxiliary, 0, size - 1);
this->update_element( matrix, auxiliary, 0, 0, R - 1, C - 1, size);
}
};
int main()
{
MyMatrix obj = MyMatrix();
// Define matrix of integer elements
int matrix[R][C] =
{
{4, 6, 2 , 2 },
{3, 7, 6 , 5 },
{1, 5, 6, 6 },
{5, 5, 4, 8 },
{1, 5, 12, 9 },
{7, 5, 2, 3 },
{1, 9, 8, 10 }
};
cout << "\n Before sorted spiral\n";
obj.print_matrix(matrix);
obj.sorted_spiral(matrix);
cout << "\n After sorted spiral\n";
obj.print_matrix(matrix);
return 0;
}
Output
Before sorted spiral
4 6 2 2
3 7 6 5
1 5 6 6
5 5 4 8
1 5 12 9
7 5 2 3
1 9 8 10
After sorted spiral
1 1 1 2
6 6 6 2
6 12 7 2
5 10 7 3
5 9 8 3
5 9 8 4
5 5 5 4
// Include namespace system
using System;
/*
C# program
Convert given Matrix into sorted Spiral Matrix
*/
// Define TreeNode
public class MyMatrix
{
// Displaying of the matrix elements
public void print_matrix(int row, int col, int[,] matrix)
{
for (int i = 0; i < row; ++i)
{
for (int 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 merge_elements(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++;
}
}
// Split the array elements into two parts
public void sort_element(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
sort_element(auxiliary, front, middle);
sort_element(auxiliary, middle + 1, tail);
// Combine split array into sorted way
merge_elements(auxiliary, front, tail, middle);
}
}
public void update_element(int row, int col, int[,] matrix, int[] auxiliary, int s_row, int s_col, int e_row, int e_col, int size)
{
// Left to right
for (int i = s_col; i <= e_col && size > 0; ++i)
{
matrix[s_row,i] = auxiliary[row * col - size];
size--;
}
// Top to down
for (int i = s_row + 1; i <= e_row && size > 0; ++i)
{
matrix[i,e_col] = auxiliary[row * col - size];
size--;
}
// Bottom right to bottom-left
for (int i = e_col - 1; i >= s_col && size > 0; --i)
{
matrix[e_row,i] = auxiliary[row * col - size];
size--;
}
// Bottom left to top
for (int i = e_row - 1; i > s_row && size > 0; --i)
{
matrix[i,s_row] = auxiliary[row * col - size];
size--;
}
if (s_row + 1 <= e_row - 1 && size > 0)
{
// Recursive call
update_element(row, col, matrix, auxiliary, s_row + 1, s_col + 1, e_row - 1, e_col - 1, size);
}
}
public void sorted_spiral(int row, int col, int[,] matrix)
{
int size = row * col;
if (size <= 0)
{
return;
}
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++;
}
}
sort_element(auxiliary, 0, size - 1);
update_element(row, col, matrix, auxiliary, 0, 0, row - 1, col - 1, size);
}
public static void Main(String[] args)
{
MyMatrix obj = new MyMatrix();
// Define matrix of integer elements
int[,] matrix = {
{4, 6, 2 , 2 },
{3, 7, 6 , 5 },
{1, 5, 6, 6 },
{5, 5, 4, 8 },
{1, 5, 12, 9 },
{7, 5, 2, 3 },
{1, 9, 8, 10 }
};
int row = matrix.GetLength(0);
int col = matrix.GetLength(1);
Console.Write("\n Before sorted spiral\n");
obj.print_matrix(row, col, matrix);
obj.sorted_spiral(row, col, matrix);
Console.Write("\n After sorted spiral\n");
obj.print_matrix(row, col, matrix);
}
}
Output
Before sorted spiral
4 6 2 2
3 7 6 5
1 5 6 6
5 5 4 8
1 5 12 9
7 5 2 3
1 9 8 10
After sorted spiral
1 1 1 2
6 6 6 2
6 12 7 2
5 10 7 3
5 9 8 3
5 9 8 4
5 5 5 4
<?php
/*
Php program
Convert given Matrix into sorted Spiral Matrix
*/
// Define TreeNode
class MyMatrix
{
// Displaying of the matrix elements
public function print_matrix($row, $col, & $matrix)
{
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 merge_elements( & $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++;
}
}
// Split the array elements into two parts
public function sort_element( & $auxiliary, $front, $tail)
{
if ($front < $tail)
{
// Get middle location of given index
$middle = intval(($front + $tail) / 2);
// Split the array into two parts
$this->sort_element($auxiliary, $front, $middle);
$this->sort_element($auxiliary, $middle + 1, $tail);
// Combine split array into sorted way
$this->merge_elements($auxiliary, $front, $tail, $middle);
}
}
public function update_element($row, $col, & $matrix, & $auxiliary, $s_row, $s_col, $e_row, $e_col, $size)
{
// Left to right
for ($i = $s_col; $i <= $e_col && $size > 0; ++$i)
{
$matrix[$s_row][$i] = $auxiliary[$row * $col - $size];
$size--;
}
// Top to down
for ($i = $s_row + 1; $i <= $e_row && $size > 0; ++$i)
{
$matrix[$i][$e_col] = $auxiliary[$row * $col - $size];
$size--;
}
// Bottom right to bottom-left
for ($i = $e_col - 1; $i >= $s_col && $size > 0; --$i)
{
$matrix[$e_row][$i] = $auxiliary[$row * $col - $size];
$size--;
}
// Bottom left to top
for ($i = $e_row - 1; $i > $s_row && $size > 0; --$i)
{
$matrix[$i][$s_row] = $auxiliary[$row * $col - $size];
$size--;
}
if ($s_row + 1 <= $e_row - 1 && $size > 0)
{
// Recursive call
$this->update_element($row, $col, $matrix, $auxiliary, $s_row + 1, $s_col + 1, $e_row - 1, $e_col - 1, $size);
}
}
public function sorted_spiral($row, $col, & $matrix)
{
$size = $row * $col;
if ($size <= 0)
{
return;
}
$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->sort_element($auxiliary, 0, $size - 1);
$this->update_element($row, $col, $matrix, $auxiliary, 0, 0, $row - 1, $col - 1, $size);
}
}
function main()
{
$obj = new MyMatrix();
// Define matrix of integer elements
$matrix = array(
array(4, 6, 2, 2),
array(3, 7, 6, 5),
array(1, 5, 6, 6),
array(5, 5, 4, 8),
array(1, 5, 12, 9),
array(7, 5, 2, 3),
array(1, 9, 8, 10));
$row = count($matrix);
$col = count($matrix[0]);
echo "\n Before sorted spiral\n";
$obj->print_matrix($row, $col, $matrix);
$obj->sorted_spiral($row, $col, $matrix);
echo "\n After sorted spiral\n";
$obj->print_matrix($row, $col, $matrix);
}
main();
Output
Before sorted spiral
4 6 2 2
3 7 6 5
1 5 6 6
5 5 4 8
1 5 12 9
7 5 2 3
1 9 8 10
After sorted spiral
1 1 1 2
6 6 6 2
6 12 7 2
5 10 7 3
5 9 8 3
5 9 8 4
5 5 5 4
/*
Node Js program
Convert given Matrix into sorted Spiral Matrix
*/
// Define TreeNode
class MyMatrix
{
// Displaying of the matrix elements
print_matrix(row, col, matrix)
{
for (var i = 0; i < row; ++i)
{
for (var 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
merge_elements(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++;
}
}
// Split the array elements into two parts
sort_element(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.sort_element(auxiliary, front, middle);
this.sort_element(auxiliary, middle + 1, tail);
// Combine split array into sorted way
this.merge_elements(auxiliary, front, tail, middle);
}
}
update_element(row, col, matrix, auxiliary, s_row, s_col, e_row, e_col, size)
{
// Left to right
for (var i = s_col; i <= e_col && size > 0; ++i)
{
matrix[s_row][i] = auxiliary[row * col - size];
size--;
}
// Top to down
for (var i = s_row + 1; i <= e_row && size > 0; ++i)
{
matrix[i][e_col] = auxiliary[row * col - size];
size--;
}
// Bottom right to bottom-left
for (var i = e_col - 1; i >= s_col && size > 0; --i)
{
matrix[e_row][i] = auxiliary[row * col - size];
size--;
}
// Bottom left to top
for (var i = e_row - 1; i > s_row && size > 0; --i)
{
matrix[i][s_row] = auxiliary[row * col - size];
size--;
}
if (s_row + 1 <= e_row - 1 && size > 0)
{
// Recursive call
this.update_element(row, col, matrix, auxiliary, s_row + 1, s_col + 1, e_row - 1, e_col - 1, size);
}
}
sorted_spiral(row, col, matrix)
{
var size = row * col;
if (size <= 0)
{
return;
}
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.sort_element(auxiliary, 0, size - 1);
this.update_element(row, col, matrix, auxiliary, 0, 0, row - 1, col - 1, size);
}
}
function main()
{
var obj = new MyMatrix();
// Define matrix of integer elements
var matrix = [
[4, 6, 2, 2] ,
[3, 7, 6, 5] ,
[1, 5, 6, 6] ,
[5, 5, 4, 8] ,
[1, 5, 12, 9] ,
[7, 5, 2, 3] ,
[1, 9, 8, 10]
];
var row = matrix.length;
var col = matrix[0].length;
process.stdout.write("\n Before sorted spiral\n");
obj.print_matrix(row, col, matrix);
obj.sorted_spiral(row, col, matrix);
process.stdout.write("\n After sorted spiral\n");
obj.print_matrix(row, col, matrix);
}
main();
Output
Before sorted spiral
4 6 2 2
3 7 6 5
1 5 6 6
5 5 4 8
1 5 12 9
7 5 2 3
1 9 8 10
After sorted spiral
1 1 1 2
6 6 6 2
6 12 7 2
5 10 7 3
5 9 8 3
5 9 8 4
5 5 5 4
# Python 3 program
# Convert given Matrix into sorted Spiral Matrix
# Define TreeNode
class MyMatrix :
# Displaying of the matrix elements
def print_matrix(self, row, col, matrix) :
i = 0
while (i < row) :
j = 0
while (j < col) :
print(" ", matrix[i][j], end = "")
j += 1
print("\n", end = "")
i += 1
print("\n", end = "")
# Sorted merge of given two subarrays of an array
def merge_elements(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
# Split the array elements into two parts
def sort_element(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.sort_element(auxiliary, front, middle)
self.sort_element(auxiliary, middle + 1, tail)
# Combine split array into sorted way
self.merge_elements(auxiliary, front, tail, middle)
def update_element(self, row, col, matrix, auxiliary, s_row, s_col, e_row, e_col, size) :
# Left to right
i = s_col
while (i <= e_col and size > 0) :
matrix[s_row][i] = auxiliary[row * col - size]
size -= 1
i += 1
# Top to down
i = s_row + 1
while (i <= e_row and size > 0) :
matrix[i][e_col] = auxiliary[row * col - size]
size -= 1
i += 1
# Bottom right to bottom-left
i = e_col - 1
while (i >= s_col and size > 0) :
matrix[e_row][i] = auxiliary[row * col - size]
size -= 1
i -= 1
# Bottom left to top
i = e_row - 1
while (i > s_row and size > 0) :
matrix[i][s_row] = auxiliary[row * col - size]
size -= 1
i -= 1
if (s_row + 1 <= e_row - 1 and size > 0) :
# Recursive call
self.update_element(row, col, matrix, auxiliary, s_row + 1, s_col + 1, e_row - 1, e_col - 1, size)
def sorted_spiral(self, row, col, matrix) :
size = row * col
if (size <= 0) :
return
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.sort_element(auxiliary, 0, size - 1)
self.update_element(row, col, matrix, auxiliary, 0, 0, row - 1, col - 1, size)
def main() :
obj = MyMatrix()
# Define matrix of integer elements
matrix = [
[4, 6, 2, 2] ,
[3, 7, 6, 5] ,
[1, 5, 6, 6] ,
[5, 5, 4, 8] ,
[1, 5, 12, 9] ,
[7, 5, 2, 3] ,
[1, 9, 8, 10]
]
row = len(matrix)
col = len(matrix[0])
print("\n Before sorted spiral\n", end = "")
obj.print_matrix(row, col, matrix)
obj.sorted_spiral(row, col, matrix)
print("\n After sorted spiral\n", end = "")
obj.print_matrix(row, col, matrix)
if __name__ == "__main__": main()
Output
Before sorted spiral
4 6 2 2
3 7 6 5
1 5 6 6
5 5 4 8
1 5 12 9
7 5 2 3
1 9 8 10
After sorted spiral
1 1 1 2
6 6 6 2
6 12 7 2
5 10 7 3
5 9 8 3
5 9 8 4
5 5 5 4
# Ruby program
# Convert given Matrix into sorted Spiral Matrix
# Define TreeNode
class MyMatrix
# Displaying of the matrix elements
def print_matrix(row, col, matrix)
i = 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 merge_elements(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
# Split the array elements into two parts
def sort_element(auxiliary, front, tail)
if (front < tail)
# Get middle location of given index
middle = (front + tail) / 2
# Split the array into two parts
self.sort_element(auxiliary, front, middle)
self.sort_element(auxiliary, middle + 1, tail)
# Combine split array into sorted way
self.merge_elements(auxiliary, front, tail, middle)
end
end
def update_element(row, col, matrix, auxiliary, s_row, s_col, e_row, e_col, size)
# Left to right
i = s_col
while (i <= e_col && size > 0)
matrix[s_row][i] = auxiliary[row * col - size]
size -= 1
i += 1
end
# Top to down
i = s_row + 1
while (i <= e_row && size > 0)
matrix[i][e_col] = auxiliary[row * col - size]
size -= 1
i += 1
end
# Bottom right to bottom-left
i = e_col - 1
while (i >= s_col && size > 0)
matrix[e_row][i] = auxiliary[row * col - size]
size -= 1
i -= 1
end
# Bottom left to top
i = e_row - 1
while (i > s_row && size > 0)
matrix[i][s_row] = auxiliary[row * col - size]
size -= 1
i -= 1
end
if (s_row + 1 <= e_row - 1 && size > 0)
# Recursive call
self.update_element(row, col, matrix, auxiliary, s_row + 1, s_col + 1, e_row - 1, e_col - 1, size)
end
end
def sorted_spiral(row, col, matrix)
size = row * col
if (size <= 0)
return
end
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.sort_element(auxiliary, 0, size - 1)
self.update_element(row, col, matrix, auxiliary, 0, 0, row - 1, col - 1, size)
end
end
def main()
obj = MyMatrix.new()
# Define matrix of integer elements
matrix = [
[4, 6, 2, 2] ,
[3, 7, 6, 5] ,
[1, 5, 6, 6] ,
[5, 5, 4, 8] ,
[1, 5, 12, 9] ,
[7, 5, 2, 3] ,
[1, 9, 8, 10]
]
row = matrix.length
col = matrix[0].length
print("\n Before sorted spiral\n")
obj.print_matrix(row, col, matrix)
obj.sorted_spiral(row, col, matrix)
print("\n After sorted spiral\n")
obj.print_matrix(row, col, matrix)
end
main()
Output
Before sorted spiral
4 6 2 2
3 7 6 5
1 5 6 6
5 5 4 8
1 5 12 9
7 5 2 3
1 9 8 10
After sorted spiral
1 1 1 2
6 6 6 2
6 12 7 2
5 10 7 3
5 9 8 3
5 9 8 4
5 5 5 4
/*
Scala program
Convert given Matrix into sorted Spiral Matrix
*/
// Define TreeNode
class MyMatrix
{
// Displaying of the matrix elements
def print_matrix(row: Int, col: Int, matrix: Array[Array[Int]]): Unit = {
var i: Int = 0;
while (i < row)
{
var j: Int = 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 merge_elements(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;
}
}
// Split the array elements into two parts
def sort_element(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.sort_element(auxiliary, front, middle);
this.sort_element(auxiliary, middle + 1, tail);
// Combine split array into sorted way
this.merge_elements(auxiliary, front, tail, middle);
}
}
def update_element(row: Int,
col: Int,
matrix: Array[Array[Int]],
auxiliary: Array[Int],
s_row: Int, s_col: Int,
e_row: Int, e_col: Int,
s: Int): Unit = {
var size = s;
// Left to right
var i: Int = s_col;
while (i <= e_col && size > 0)
{
matrix(s_row)(i) = auxiliary(row * col - size);
size = size - 1;
i += 1;
}
// Top to down
i = s_row + 1;
while (i <= e_row && size > 0)
{
matrix(i)(e_col) = auxiliary(row * col - size);
size = size - 1;
i += 1;
}
// Bottom right to bottom-left
i = e_col - 1;
while (i >= s_col && size > 0)
{
matrix(e_row)(i) = auxiliary(row * col - size);
size = size - 1;
i -= 1;
}
// Bottom left to top
i = e_row - 1;
while (i > s_row && size > 0)
{
matrix(i)(s_row) = auxiliary(row * col - size);
size = size - 1;
i -= 1;
}
if (s_row + 1 <= e_row - 1 && size > 0)
{
// Recursive call
this.update_element(row, col, matrix, auxiliary, s_row + 1, s_col + 1, e_row - 1, e_col - 1, size);
}
}
def sorted_spiral(row: Int, col: Int, matrix: Array[Array[Int]]): Unit = {
var size: Int = row * col;
if (size <= 0)
{
return;
}
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.sort_element(auxiliary, 0, size - 1);
this.update_element(row, col, matrix, auxiliary, 0, 0, row - 1, col - 1, size);
}
}
object Main
{
def main(args: Array[String]): Unit = {
var obj: MyMatrix = new MyMatrix();
// Define matrix of integer elements
var matrix: Array[Array[Int]] = Array(
Array(4, 6, 2, 2),
Array(3, 7, 6, 5),
Array(1, 5, 6, 6),
Array(5, 5, 4, 8),
Array(1, 5, 12, 9),
Array(7, 5, 2, 3),
Array(1, 9, 8, 10));
var row: Int = matrix.length;
var col: Int = matrix(0).length;
print("\n Before sorted spiral\n");
obj.print_matrix(row, col, matrix);
obj.sorted_spiral(row, col, matrix);
print("\n After sorted spiral\n");
obj.print_matrix(row, col, matrix);
}
}
Output
Before sorted spiral
4 6 2 2
3 7 6 5
1 5 6 6
5 5 4 8
1 5 12 9
7 5 2 3
1 9 8 10
After sorted spiral
1 1 1 2
6 6 6 2
6 12 7 2
5 10 7 3
5 9 8 3
5 9 8 4
5 5 5 4
/*
Swift 4 program
Convert given Matrix into sorted Spiral Matrix
*/
// Define TreeNode
class MyMatrix
{
// Displaying of the matrix elements
func print_matrix(_ row: Int, _ col: Int, _ matrix: [[Int]])
{
var i: Int = 0;
while (i < row)
{
var j: Int = 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 merge_elements(_ 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;
}
}
// Split the array elements into two parts
func sort_element(_ 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.sort_element(&auxiliary, front, middle);
self.sort_element(&auxiliary, middle + 1, tail);
// Combine split array into sorted way
self.merge_elements(&auxiliary, front, tail, middle);
}
}
func update_element(_ row: Int,
_ col: Int, _ matrix: inout[[Int]],
_ auxiliary:inout [Int], _ s_row: Int,
_ s_col: Int, _ e_row: Int,
_ e_col: Int, _ s: Int)
{
var size = s;
// Left to right
var i: Int = s_col;
while (i <= e_col && size > 0)
{
matrix[s_row][i] = auxiliary[row * col - size];
size -= 1;
i += 1;
}
// Top to down
i = s_row + 1;
while (i <= e_row && size > 0)
{
matrix[i][e_col] = auxiliary[row * col - size];
size -= 1;
i += 1;
}
// Bottom right to bottom-left
i = e_col - 1;
while (i >= s_col && size > 0)
{
matrix[e_row][i] = auxiliary[row * col - size];
size -= 1;
i -= 1;
}
// Bottom left to top
i = e_row - 1;
while (i > s_row && size > 0)
{
matrix[i][s_row] = auxiliary[row * col - size];
size -= 1;
i -= 1;
}
if (s_row + 1 <= e_row - 1 && size > 0)
{
// Recursive call
self.update_element(row, col, &matrix, &auxiliary, s_row + 1, s_col + 1, e_row - 1, e_col - 1, size);
}
}
func sorted_spiral(_ row: Int, _ col: Int, _ matrix: inout[[Int]])
{
let size: Int = row * col;
if (size <= 0)
{
return;
}
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.sort_element(&auxiliary, 0, size - 1);
self.update_element(row, col, &matrix, &auxiliary, 0, 0, row - 1, col - 1, size);
}
}
func main()
{
let obj: MyMatrix = MyMatrix();
// Define matrix of integer elements
var matrix: [[Int]] = [
[4, 6, 2, 2] ,
[3, 7, 6, 5] ,
[1, 5, 6, 6] ,
[5, 5, 4, 8] ,
[1, 5, 12, 9] ,
[7, 5, 2, 3] ,
[1, 9, 8, 10]
];
let row: Int = matrix.count;
let col: Int = matrix[0].count;
print("\n Before sorted spiral\n", terminator: "");
obj.print_matrix(row, col, matrix);
obj.sorted_spiral(row, col, &matrix);
print("\n After sorted spiral\n", terminator: "");
obj.print_matrix(row, col, matrix);
}
main();
Output
Before sorted spiral
4 6 2 2
3 7 6 5
1 5 6 6
5 5 4 8
1 5 12 9
7 5 2 3
1 9 8 10
After sorted spiral
1 1 1 2
6 6 6 2
6 12 7 2
5 10 7 3
5 9 8 3
5 9 8 4
5 5 5 4
/*
Kotlin program
Convert given Matrix into sorted Spiral Matrix
*/
// Define TreeNode
class MyMatrix
{
// Displaying of the matrix elements
fun print_matrix(row: Int, col: Int, matrix: Array < Array < Int >> ): Unit
{
var i: Int = 0;
while (i < row)
{
var j: Int = 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 merge_elements(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;
}
}
// Split the array elements into two parts
fun sort_element(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.sort_element(auxiliary, front, middle);
this.sort_element(auxiliary, middle + 1, tail);
// Combine split array into sorted way
this.merge_elements(auxiliary, front, tail, middle);
}
}
fun update_element(row: Int, col: Int,
matrix: Array <Array<Int>> ,
auxiliary: Array < Int > ,
s_row: Int, s_col: Int,
e_row: Int, e_col: Int,
s: Int): Unit
{
var size = s;
// Left to right
var i: Int = s_col;
while (i <= e_col && size > 0)
{
matrix[s_row][i] = auxiliary[row * col - size];
size = size - 1;
i += 1;
}
// Top to down
i = s_row + 1;
while (i <= e_row && size > 0)
{
matrix[i][e_col] = auxiliary[row * col - size];
size = size - 1;
i += 1;
}
// Bottom right to bottom-left
i = e_col - 1;
while (i >= s_col && size > 0)
{
matrix[e_row][i] = auxiliary[row * col - size];
size = size - 1;
i -= 1;
}
// Bottom left to top
i = e_row - 1;
while (i > s_row && size > 0)
{
matrix[i][s_row] = auxiliary[row * col - size];
size = size - 1;
i -= 1;
}
if (s_row + 1 <= e_row - 1 && size > 0)
{
// Recursive call
this.update_element(row, col, matrix, auxiliary, s_row + 1, s_col + 1, e_row - 1, e_col - 1, size);
}
}
fun sorted_spiral(row: Int, col: Int, matrix: Array < Array < Int >> ): Unit
{
var size: Int = row * col;
if (size <= 0)
{
return;
}
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.sort_element(auxiliary, 0, size - 1);
this.update_element(row, col, matrix, auxiliary, 0, 0, row - 1, col - 1, size);
}
}
fun main(args: Array < String > ): Unit
{
var obj: MyMatrix = MyMatrix();
// Define matrix of integer elements
var matrix: Array<Array<Int>> = arrayOf(
arrayOf(4, 6, 2, 2),
arrayOf(3, 7, 6, 5),
arrayOf(1, 5, 6, 6),
arrayOf(5, 5, 4, 8),
arrayOf(1, 5, 12, 9),
arrayOf(7, 5, 2, 3),
arrayOf(1, 9, 8, 10));
var row: Int = matrix.count();
var col: Int = matrix[0].count();
print("\n Before sorted spiral\n");
obj.print_matrix(row, col, matrix);
obj.sorted_spiral(row, col, matrix);
print("\n After sorted spiral\n");
obj.print_matrix(row, col, matrix);
}
Output
Before sorted spiral
4 6 2 2
3 7 6 5
1 5 6 6
5 5 4 8
1 5 12 9
7 5 2 3
1 9 8 10
After sorted spiral
1 1 1 2
6 6 6 2
6 12 7 2
5 10 7 3
5 9 8 3
5 9 8 4
5 5 5 4
Output Explanation
The given Java code implements the above algorithm to convert the given matrix into a sorted spiral matrix. It prints the original matrix and the sorted spiral 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 traverses all the elements of the matrix once to collect them in the auxiliary array, which takes O(row * col) time. Then, the merge sort 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, which takes 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