Transposing a matrix using c++

Question

I want to write a program to transpose a n*n matrix, but the code output something wired. It did not transpose the matrix. suppose I want to transpose a matrix{(1,2,3), {4,5,6),(7,8,9)}, the result is basically the same as the original one with some strange behavior which I have no knowledge of.

#include<iostream>
#include<iomanip>
using namespace std;
void transpose(int* p, int n);
#define M 20
int main()
{
    int a[M][M];
    int n;      
    int* p;
    cout << "The size of a matrix is: ";
    cin >> n;
    cout << "Input a matrix: " << endl;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> a[i][j];
    p = &a[0][0];
    transpose(p, n);
    cout << "Now, the matrix is: " << endl;
    for (int i = 0; i < n; i++)
    {

        for (int j = 0; j < n; j++)
        {
            cout << setw(4) << a[i][j];
        }
        cout << endl;
    }
    return 0;
}

void transpose(int* p, int n)
{
    for (int i = 0; i < n; i++)
    {
        for (int j = i; j < n; j++)
        {
            int temp = *(p + i * n + j);
            *(p + i * n + j) = *(p + j * n + i);
            *(p + j * n + i) = temp;
        }
    }
}

Answer 1

You should call:

transpose(p, M);

instead of:

transpose(p, n);

Although your matrix is 3x3, you reserved memory for a 20x20 matrix. So the next row is 20 ints away from that (the memory gap between two row offsets is called the stride).

To speed up the process, you can implement a three-parameter variant:

void transpose(int* p, int m, int n) {
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            int temp = *(p + i * m + j);
            *(p + i * m + j) = *(p + j * m + i);
            *(p + j * m + i) = temp;
        }
    }
}

and call with:

transpose(p, M, n);

But to be honest, I think the way you define the matrix in memory as well as the transpose algorithm can be improved. Your transpose method is not really cache-friendly. For fast computations, I would advice the LAPACK package. Such algorithms work block-wise to reduce the number of cache-faults significantly and in make use of multithreading as well to boost performance. See this lecture for more details on how to transpose a matrix efficiently.