How to transpose a 2 dimensional array on C via call by reference?

Question

As the title says, I am trying to transpose a 2 dimensional matrix by calling by reference. I have attached my code below. When I run the code, the 2 dimensional array is unchanged.

#include <stdio.h>

#define SIZE 4

void transpose2D(int ar[][SIZE], int rowSize, int colSize);

int main()
{

    int testArr[4][4] = {
        {1, 2, 3, 4},
        {5, 1, 2, 2},
        {6, 3, 4, 4},
        {7, 5, 6, 7},
    };

    transpose2D(testArr, 4, 4);

    // print out new array
    for (int i = 0; i < 4; i++)
    {

        for (int j = 0; j < 4; j++)
        {
            printf("%d ", testArr[i][j]);
        }

        printf("\n");
    }

    return 0;
}

void transpose2D(int ar[][SIZE], int rowSize, int colSize)
{

    for (int i = 0; i < rowSize; i++)
    {
        for (int j = 0; j < colSize; j++)
        {
            int temp = *(*(ar + i) + j);
            *(*(ar + i) + j) = *(*(ar + j) + i);
            *(*(ar + j) + i) = temp;
        }
    }
}

Have been stuck for a couple of hours, any help is greatly appreciated, thank you!

For any pointer or array `ar` and index `i`, the expression `*(ar + i)` is *exactly* equal to `ar[i]`. So instead of `*(*(ar + i) + j)` you can use `ar[i][j]`. — Some programmer dude, Oct 14 '21 at 08:51
I'm finding this a little tricky to follow. Is there a particular reason you're using `*(*(ar + i) + j)` instead of the simpler `ar[i][j]`? — Alexander, Oct 14 '21 at 08:51
Both expression are *exactly* equal, it doesn't matter if `ar` is a pointer or an array. In your case, because `ar` is a pointer, `ar[i][j]` will be using pointers. — Some programmer dude, Oct 14 '21 at 08:53
As for your problem, you probably swap each element *twice*. Use a debugger to step through the code, and write down on paper which elements you swap. — Some programmer dude, Oct 14 '21 at 08:53
Yup, realised that I am swapping the same values twice. Will work towards solving that, thanks! — pjyamas, Oct 14 '21 at 09:04
Read this: [Do pointers support "array style indexing"?](https://stackoverflow.com/questions/55747822/do-pointers-support-array-style-indexing) — Lundin, Oct 14 '21 at 09:31
https://gustedt.wordpress.com/2014/09/08/dont-use-fake-matrices/ — Chef Gladiator, Oct 14 '21 at 10:26
As written, your routine `transpose2D` works on submatrixes of dimensions `rowSize`×`colSize` that are embedded in a full matrix of (apparently) `SIZE`×`SIZE`. If that is the intent, then the submatrix and its transpose will have two parts: A common square at the top-left where they overlap, and you need to swap elements from the upper triangle with the lower triangle, and a separate part transposing between a rectangle at the bottom left with a rectangle at the top right. For the rectangles, you need to move, not swap. If that is not the intent, edit the post to clarify what cases to support. — Eric Postpischil, Oct 14 '21 at 10:39
If it is the intent, then I suggest you work on supporting only square submatrices first, then add code to handle the rectangles. — Eric Postpischil, Oct 14 '21 at 10:40
Please correct your transpose procedure. As it stands, it does transpose two times, resulting in no transpose at all. The `j` loop should not read `j=0; j — Chef Gladiator, Oct 14 '21 at 10:54
I’m voting to close this question because this is home task question — Cy-4AH, Oct 18 '21 at 17:17

tstanisl · Answer 1 · 2021-10-14T10:35:24.687

0

To fix your function I suggest:

switch element only once, the previous version swapped elements for i=a, j=b and i=b,j=a, so the matrix remained unchanged
use a common a[i][j] syntax
let the non-square matrix be embedded into a larger matrix whose inner dimensions is set to stride.
using VLAs to make the interface a bit more generic

void transpose2D(size_t rows, size_t cols, size_t stride, int ar[][stride]) {
    assert(rows <= stride);
    assert(cols <= stride);
    for (size_t i = 0; i < rows; i++) {
        for (size_t j = i + 1; j < cols; j++) {
            int tmp = ar[j][i];
            ar[j][i] = ar[i][j];
            ar[i][j] = tmp;
        }
    }
}

Exemplary usage:

int testArr[4][4] = {
        {1, 2},
        {5, 1},
        {6, 3},
    };

transpose2D(3, 2, 4, testArr);

The algorithm is still very inefficient due to terrible cache miss rates on access to a[j][i]. It can be fixes by tiling and transposing smaller 8x8 blocks, but it is a topic for another day.

edited Oct 14 '21 at 10:35

answered Oct 14 '21 at 09:29

tstanisl

13,520
2
25
40

There is no need for the matrix to be square because it is a submatrix embedded a larger matrix that is already square, so the memory layout is fine. Making the alterations you show breaks the ability of the routine to accept non-square matrices. – Eric Postpischil Oct 14 '21 at 09:58
Cache issues are well beyond the level of this assignment and are a distraction here. – Eric Postpischil Oct 14 '21 at 09:59
@EricPostpischil, the way the question is stated I'm pretty sure that OP wants to transpose the whole array. – tstanisl Oct 14 '21 at 10:06
@EricPostpischil, and note that the proposed API only requires the first dimensions to have *at least* `size` elements. It can be longer that this – tstanisl Oct 14 '21 at 10:11
The new code may get correct results for rectangular matrices (embedded in square matrices), but it is wasteful since elements outside the square that is common between the matrix and its transpose only need to be moved, not swapped. – Eric Postpischil Oct 14 '21 at 10:43
Re “the proposed API only requires”: This is irrelevant; no element beyond `SIZE` rows could be transposed since there is no column for it to move into. As long as we are transposing a submatrix embedded in a containing matrix, the usable part of the containing matrix is limited to a square of its smaller dimension. – Eric Postpischil Oct 14 '21 at 10:46

How to transpose a 2 dimensional array on C via call by reference?

1 Answers1