Rearranging rows in dynamically allocated 2D array in C

Question

I'm currently working on a program in C where I input matrix dimensions and elements of a matrix, which is represented in memory as dynamic 2D array. Program later finds maximum of each row. Then it finds minimal maximum out of maximums of all rows.

For example, if we have 3x3 matrix:
1 2 3
7 8 9
4 5 6

maximums are 3, 9, 6 and minimal maximum is 3. If minimal maximum is positive, program should proceed with rearranging order of rows so they follow ascending order of maximums, so the final output should be:

1 2 3
4 5 6
7 8 9

I made a dynamic array which contains values of maximums followed by row in which they were found, for example: 3 0 6 1 9 2. But I have no idea what should I do next. It crossed my mind if I somehow figure out a way to use this array with indices I made that I would be in problem if I have same maximum values in different rows, for example if matrix was:

1 2 3
4 5 6
7 8 9
1 1 6

my array would be 3 0 6 1 9 2 6 3. I would then need additional array for positions and it becomes like an inception. Maybe I could use some flag to see if I've already encountered the same number, but I generally, like algorithmically, don't know what to do. It crossed my mind to make an array and transfer values to it, but it would waste additional space... If I found a way to find order in which I would like to print rows, would I need an adress function different than one I already have? (which is, in double for loop, for current element - *(matrix+i * numOfCols+currentCol) ) I would appreciate if somebody told me am I thinking correctly about problem solution and give me some advice about this problem. Thanks in advance!

Answer 1

Array is not dynamic because we can not change the size of array, so in this case you can use double pointer, for example, int **matrix to store the value of 2D array.

The function for searching the max value of each row and the row index of each max value:

int * max_of_row(int n, int m, int **mat) {
    // allocate for n row and the row index of max value
    int *matrix = malloc (sizeof(int) * n*2);

    for(int i = 0; i < 2*n; i++) {
        matrix[i] = 0;
    }

    int k = 0;

    for(int i = 0; i < n; i++) {    
        for (int j = 0; j < m; j++) {
            if(matrix[k] < mat[i][j]) {
                matrix[k] = mat[i][j];
            }
        }
        matrix[k+1] = i;
        k += 2;
    }

    return matrix;
}

The main function for test:

int main(int argc, char const *argv[])
{
    // allocate for 4 rows
    int **matrix  = malloc (sizeof (int) * 4);
    for (int i = 0; i < 4; i++) {
        // allocate for 3 cols
        matrix[i] = malloc(sizeof(int) * 3);
        for(int j = 0; j < 3; j++){
            matrix[i][j] = i+j;
        }
    }


    int * mat = max_of_row(4, 3,matrix);

    printf("matrix:\n");
    for (int i = 0; i < 4; i++) {
        for(int j = 0; j < 3; j++){
            printf("%d ",matrix[i][j]);
        }
        printf("\n");
    }
    printf("max of row and positon\n");
    for (int i = 0; i < 8; i++) {
        printf("%d ", mat[i]);
    }
    printf("\nmax of row\n");
    for (int i = 0; i < 8; i += 2) {
        printf("%d ", mat[i]);
    }

    printf("\n");
    return 0;
}

Output:

matrix:
0 1 2 
1 2 3 
2 3 4 
3 4 5 
max of row and positon
2 0 3 1 4 2 5 3 
max of row
2 3 4 5

Answer 2

I don't know if I have understood it correctly, but what you want to do is to rearrange the matrix, arranging the rows by the greatest maximum to the least... First, I don't think you need the dynamic array, because the maximums are already ordered, and their position on the array is enough to describe the row in which they are. To order from maximum to minimum, I would make a loop which saved the position of the maximum and then, use it to store the correspondent row in the input matrix into the output matrix. Then, change the value of that maximum to 0 (if you include 0 in positives, then change to -1), and repeat the process until all rows have been passed to the output matrix. Here is a sketch of what it would look like:

for(k = 0; k < n_rows; ++k)
     for(i = 0; i < n_rows; ++i)
          if (max[i] > current_max)
               current_max = max[i];
               max_row = i;
     for(c = 0; c < n_columns; ++c)
          output_matrix[row][c] = inputmatrix[max_row][c];
     max[max_row] = 0;