***IN C LANGUAGE with no errors detected /* Sort a matrix of size N times M in d
ID: 3856089 • Letter: #
Question
***IN C LANGUAGE with no errors detected
/* Sort a matrix of size N times M in descending order. i.e. A[0] [0] would have the largest value and A [N] [M] would have the smallest value. Example of a 3 times 3 sort: 9 8 7 6 5 4 3 2 1 */ int SortMatrix (int A [] [], unsigned int rowsize, unsigned int colsize): /* Given a matrix of size N times M sorted in descending order and value V, write a function which returns -1 if value V is not in the matrix, else it returns 1 if V is in the matrix. The function also computes the position of V in the matrix, that is P = [R, C], where R is the row number of V and C is the column number of V in the matrix, is V is in the matrix (if V is not in the matrix then P = [-1, -1]): P is a 1D array of size 2. You must use the recursive Binary Search method. */ int SearchMatrix (int A [] [], int V, int *P, unsigned int rowsize, unsigned int colsize): Write a main program which: a. reads a matrix of size N times M containing random integers between 0 and 100: b. sort the matrix in descending order: c. ask the user for a value V and search for V in matrix: in which case, the function will compute the position of V as P = [R, C] and return -1 or +1 depending if V is in A or not.Explanation / Answer
Given below is the code with output. In case of any issues, please post a comment. If the answer helped, please rate it. Thank you.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void SortMatrix(int A[][5], unsigned int rowSize, unsigned int colSize);
void Initialize(int A[][5], unsigned int rowSize, unsigned int colSize);
void Print(int A[][5], unsigned int rowSize, unsigned int colSize);
int SearchMatrix(int A[][5], int V, int *P,unsigned int rowSize, unsigned int colSize);
void GetRowColumn(int position , int *row, int *col, int columnSize);
int main()
{
int A[4][5];
int V, P[2];
char ans[2];
Initialize(A, 4, 5);
printf(" Before sorting the matrix is ");
Print(A, 4, 5);
printf(" Sorting matrix...");
SortMatrix(A, 4, 5);
printf(" After sorting the matrix is ");
Print(A, 4, 5);
do
{
printf(" Which number do you want to search? ");
scanf("%d", &V);
if(SearchMatrix(A, V, P, 4, 5) == 1)
{
printf(" Found %d at (%d, %d) *** 0 based index for row & col ***", V, P[0], P[1]);
}
else
{
printf(" Not found %d", V);
}
printf(" Search another number ( y/n )? ");
scanf("%s", ans);
}while(ans[0] == 'y' || ans[0] == 'Y');
}
/*given a position, maps it to row and col depending on number of elements in each row i.e. columnSize*/
void GetRowColumn(int position, int *row, int *col, int columnSize)
{
*row = position / columnSize;
*col = position % columnSize;
}
void SortMatrix(int A[][5], unsigned int rowSize, unsigned int colSize)
{
int size = rowSize * colSize;
int pos1, pos2;
int r1, c1, r2, c2;
int minIdx;
int temp;
//use selection sort as if the 2D array were mapped to 1D array, order by rows
//find the mapping number from 2D to 1D postion
for( pos1 = 0; pos1 < size; pos1++)
{
minIdx = pos1;
GetRowColumn(pos1, &r1, &c1, colSize);
for(pos2 = pos1 + 1; pos2 < size; pos2++)
{
//find the correspond elements in 2D for pos1 and pos2
GetRowColumn(pos2, &r2, &c2, colSize);
if(A[r2][c2] > A[r1][c1])
{
minIdx = pos2;
r1 = r2;
c1 = c2;
}
}
if(minIdx != pos1)
{
GetRowColumn(pos1, &r2, &c2, colSize);
temp = A[r2][c2];
A[r2][c2] = A[r1][c1];
A[r1][c1] = temp;
}
}
}
void Initialize(int A[][5], unsigned int rowSize, unsigned int colSize)
{
int i,j;
srand(time(NULL));
for(i = 0; i < rowSize; i++)
{
for(j = 0; j < colSize; j++)
A[i][j] = rand() % 101;
}
}
void Print(int A[][5], unsigned int rowSize, unsigned int colSize)
{
int i, j;
for( i = 0; i < rowSize; i++)
{
printf(" ");
for(j = 0; j < colSize; j++)
{
printf("%6d", A[i][j]);
}
}
printf(" ");
}
int SearchMatrix(int A[][5], int V, int *P,unsigned int rowSize, unsigned int colSize)
{
int start = 0 , end = rowSize * colSize - 1;
int mid;
int r, c;
while(start <= end)
{
mid = (start + end) / 2;
GetRowColumn(mid, &r, &c, colSize);
//printf(" %d %d %d", start, end, A[r][c]);
if(A[r][c] == V)
{
P[0] = r;
P[1] = c;
return 1;
}
else if(V < A[r][c] )
{
start = mid + 1;
}
else
{
end = mid - 1;
}
}
//not found
P[0] = -1;
P[1] = -1;
return -1;
}
output
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void SortMatrix(int A[][5], unsigned int rowSize, unsigned int colSize);
void Initialize(int A[][5], unsigned int rowSize, unsigned int colSize);
void Print(int A[][5], unsigned int rowSize, unsigned int colSize);
int SearchMatrix(int A[][5], int V, int *P,unsigned int rowSize, unsigned int colSize);
void GetRowColumn(int position , int *row, int *col, int columnSize);
int main()
{
int A[4][5];
int V, P[2];
char ans[2];
Initialize(A, 4, 5);
printf(" Before sorting the matrix is ");
Print(A, 4, 5);
printf(" Sorting matrix...");
SortMatrix(A, 4, 5);
printf(" After sorting the matrix is ");
Print(A, 4, 5);
do
{
printf(" Which number do you want to search? ");
scanf("%d", &V);
if(SearchMatrix(A, V, P, 4, 5) == 1)
{
printf(" Found %d at (%d, %d) *** 0 based index for row & col ***", V, P[0], P[1]);
}
else
{
printf(" Not found %d", V);
}
printf(" Search another number ( y/n )? ");
scanf("%s", ans);
}while(ans[0] == 'y' || ans[0] == 'Y');
}
/*given a position, maps it to row and col depending on number of elements in each row i.e. columnSize*/
void GetRowColumn(int position, int *row, int *col, int columnSize)
{
*row = position / columnSize;
*col = position % columnSize;
}
void SortMatrix(int A[][5], unsigned int rowSize, unsigned int colSize)
{
int size = rowSize * colSize;
int pos1, pos2;
int r1, c1, r2, c2;
int minIdx;
int temp;
//use selection sort as if the 2D array were mapped to 1D array, order by rows
//find the mapping number from 2D to 1D postion
for( pos1 = 0; pos1 < size; pos1++)
{
minIdx = pos1;
GetRowColumn(pos1, &r1, &c1, colSize);
for(pos2 = pos1 + 1; pos2 < size; pos2++)
{
//find the correspond elements in 2D for pos1 and pos2
GetRowColumn(pos2, &r2, &c2, colSize);
if(A[r2][c2] > A[r1][c1])
{
minIdx = pos2;
r1 = r2;
c1 = c2;
}
}
if(minIdx != pos1)
{
GetRowColumn(pos1, &r2, &c2, colSize);
temp = A[r2][c2];
A[r2][c2] = A[r1][c1];
A[r1][c1] = temp;
}
}
}
void Initialize(int A[][5], unsigned int rowSize, unsigned int colSize)
{
int i,j;
srand(time(NULL));
for(i = 0; i < rowSize; i++)
{
for(j = 0; j < colSize; j++)
A[i][j] = rand() % 101;
}
}
void Print(int A[][5], unsigned int rowSize, unsigned int colSize)
{
int i, j;
for( i = 0; i < rowSize; i++)
{
printf(" ");
for(j = 0; j < colSize; j++)
{
printf("%6d", A[i][j]);
}
}
printf(" ");
}
int SearchMatrix(int A[][5], int V, int *P,unsigned int rowSize, unsigned int colSize)
{
int start = 0 , end = rowSize * colSize - 1;
int mid;
int r, c;
while(start <= end)
{
mid = (start + end) / 2;
GetRowColumn(mid, &r, &c, colSize);
//printf(" %d %d %d", start, end, A[r][c]);
if(A[r][c] == V)
{
P[0] = r;
P[1] = c;
return 1;
}
else if(V < A[r][c] )
{
start = mid + 1;
}
else
{
end = mid - 1;
}
}
//not found
P[0] = -1;
P[1] = -1;
return -1;
}
output
Before sorting the matrix is
77 62 28 54 85
54 69 76 91 88
77 82 35 5 86
70 1 45 1 97
Sorting matrix...
After sorting the matrix is
97 91 88 86 85
82 77 77 76 70
69 62 54 54 45
35 28 5 1 1
Which number do you want to search? 69
Found 69 at (2, 0) *** 0 based index for row & col ***
Search another number ( y/n )? y
Which number do you want to search? 1
Found 1 at (3, 3) *** 0 based index for row & col ***
Search another number ( y/n )? y
Which number do you want to search? 99
Not found 99
Search another number ( y/n )? y
Which number do you want to search? 50
Not found 50
Search another number ( y/n )? n
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.