I'm facing a challenge with an exercise for my computer science course, and I could use some assistance. The exercise prompt states: 'Write a function in C that takes a matrix of floats as input and, using a recursive function that implements the Merge Sort algorithm, sorts the elements of each row of the matrix in ascending order (without using auxiliary matrices)'
Currently, I'm attempting to implement the solution, but it appears to be ineffective. When I provide the following matrix as input:
float matrix[3][3] = {
{5.2, 1.1, 3.3},
{0.8, 4.4, 2.1},
{9.6, 7.3, 1.5}
};
The output I receive is identical to the input matrix, indicating that the sorting process is not functioning correctly. I suspect that the issue lies within my implementation of the Merge Sort algorithm for sorting the elements of each row. Here is the code I have written so far:
#include <stdio.h>
#define MAX_ROWS 100
#define MAX_COLS 100
void initializeMatrix(int row, int col, int matrix[][MAX_COLS]) {
printf("Riempi la matrice\n");
for (int i = 0; i < row; ++i) {
for (int j = 0; j < col; ++j) {
scanf("%f", &matrix[i][j]);
}
}
}
void merge(float matrix[], int start, int mid, int end, int cols) {
int left_size = mid - start + 1;
int right_size = end - mid;
int left_offset = start * cols;
int right_offset = (mid + 1) * cols;
// Merge the two subarrays in-place
int i = 0, j = 0, k = start;
while (i < left_size && j < right_size) {
if (matrix[left_offset + i] <= matrix[right_offset + j]) {
matrix[k * cols] = matrix[left_offset + i];
i++;
} else {
matrix[k * cols] = matrix[right_offset + j];
j++;
}
k++;
}
// Copy the remaining elements of left[], if any
while (i < left_size) {
matrix[k * cols] = matrix[left_offset + i];
i++;
k++;
}
// Copy the remaining elements of right[], if any
while (j < right_size) {
matrix[k * cols] = matrix[right_offset + j];
j++;
k++;
}
}
void mergeSort(float matrix[], int start, int end, int cols) {
if (start < end) {
int mid = start + (end - start) / 2;
mergeSort(matrix, start, mid, cols);
mergeSort(matrix, mid + 1, end, cols);
merge(matrix, start, mid, end, cols);
}
}
void sortMatrixRows(float matrix[], int rows, int cols) {
for (int i = 0; i < rows; i++) {
mergeSort(matrix, i, i, cols);
}
}
void printMatrix(float matrix[][MAX_COLS], int row, int col) {
// Printing the matrix for verification
for (int i = 0; i < row; ++i) {
for (int j = 0; j < col; ++j) {
printf("%.2f ", matrix[i][j]);
}
printf("\n");
}
}
int main() {
int row, col;
printf("Insert the number of rows\n");
scanf("%d", &row);
printf("Insert the number of columns\n");
scanf("%d", &col);
float matrix[MAX_ROWS][MAX_COLS];
initializeMatrix(row, col, matrix);
printf("Original Matrix:\n");
printMatrix(matrix, row, col);
sortMatrixRows(matrix, row, col);
printf("\nSorted Matrix:\n");
printMatrix(matrix, row, col);
return 0;
}
I have tried debugging the code by adding print statements and examining the variables at various stages of the sorting process. However, I haven't been able to identify the exact problem. Any insights or suggestions on how to fix the issue and get the desired sorting behavior would be greatly appreciated. Thank you for your help!
Edit: I have identified several issues with the logic in the merge() function, which was causing the merge sort to not work correctly. Additionally, as pointed out by @chux, there was an error in the sortMatrixRows() function where I made a modification to the calling function as mergeSort(matrix, i, 0, cols - 1). By addressing these problems and making the necessary changes, I have successfully implemented the code and verified its functionality.
For reference, here is the complete and functioning code:
/* Write a function in C that takes a matrix of floats as input and, using a recursive function that implements the
Merge Sort algorithm, sorts the elements of each row of the matrix
in ascending order (without using auxiliary matrices) */
#include <stdio.h>
#define MAX_ROWS 100
#define MAX_COLS 100
void initializeMatrix(int row, int col, float matrix[][MAX_COLS]) {
printf("Fill the matrix\n");
for (int i = 0; i < row; ++i) {
for (int j = 0; j < col; ++j) {
scanf("%f", &matrix[i][j]);
}
}
}
void merge(float matrix[][MAX_COLS], int row, int start, int mid, int end) {
int start2 = mid + 1;
// If the direct predecessor of start2 is smaller than start2,
// then it means they are already in correct order.
// So, we just skip the element at start2
if (matrix[row][mid] <= matrix[row][start2]) {
return;
}
// Otherwise, we need to find the correct position of start2
// and make a room for it by moving other elements
while (start <= mid && start2 <= end) {
if (matrix[row][start] <= matrix[row][start2]) {
start++;
} else {
float value = matrix[row][start2];
int index = start2;
// Shift all the elements between element 1,
// element 2, right by 1.
while (index != start) {
matrix[row][index] = matrix[row][index - 1];
index--;
}
matrix[row][start] = value;
// Update all the pointers
start++;
mid++;
start2++;
}
}
}
void mergeSort(float matrix[][MAX_COLS], int row, int start, int end) {
// The condition 'start < end' is the base case for the recursion.
// If 'start' is not less than 'end', then the array has one or zero elements and is already sorted.
if (start < end) {
// Compute the middle of the array.
int mid = start + (end - start) / 2;
// Recursively sort the two halves of the array.
// The first half is from 'start' to 'mid'
// and the second half is from 'mid + 1' to 'end'.
mergeSort(matrix, row, start, mid);
mergeSort(matrix, row, mid + 1, end);
// After sorting the two halves, merge them into a single sorted array.
merge(matrix, row, start, mid, end);
}
}
void sortMatrixRows(float matrix[][MAX_COLS], int rows, int cols) {
for (int i = 0; i < rows; i++) {
mergeSort(matrix, i, 0, cols - 1);
}
}
void printMatrix(float matrix[][MAX_COLS], int row, int col) {
for (int i = 0; i < row; ++i) {
for (int j = 0; j < col; ++j) {
printf("%.2f ", matrix[i][j]);
}
printf("\n");
}
}
int main() {
int row, col;
printf("Insert the number of rows\n");
scanf("%d", &row);
printf("Insert the number of columns\n");
scanf("%d", &col);
float matrix[MAX_ROWS][MAX_COLS];
initializeMatrix(row, col, matrix);
printf("Original Matrix\n");
printMatrix(matrix, row, col);
sortMatrixRows(matrix, row, col);
printf("\nSorted Matrix\n");
printMatrix(matrix, row, col);
return 0;
}
I have added comments to the merge() and mergeSort() functions in order to provide a better understanding of their functionality.
Thank you @chux for the help and feel free to use it or provide feedback if you have any further questions or concerns.