title: In-Place Matrix Transpose
slug: in-place-matrix-transpose
date: 2009-07-28 11:07:16
tags: mathjax,C++ Discoveries and Notes,Programming
description:
wp-status: publish
I was looking around today for an algorithm for In-Place Matrix Transposition
and didn't manage to find anything, so this is what I came up with. I'll
analyze and document it fully later, but I just wanted to get it down.
It's wasteful in that it will repeat a lot of operations, especially for
"thin" matrices (worst case: vector). But it will work, never-the-less. Worst
case run time is at most $latex O(n^2)$ where $latex n$ is the size of the
matrix $latex n = rows times columns$
Edit: No longer arbitrarily repeating cycles ( was leading to identity
operation, duh! ).
```c++
template
void CMatrix::inPlaceTranspose( )
{
using std::swap;
resize(cols,rows);
int i, j, k, k_start, k_new;
int n = rows;
int m = cols;
int length = rows*cols;
for(k_start=1; k_start < length; k_start++)
{
T temp = data[k_start];
bool abort = false;
k_new = k = k_start;
// go through the cycle once and ensure that the starting point is
// minimal
do
{
if( k_new < k_start )
{
abort = true;
break;
}
k = k_new;
i = k%n;
j = k/n;
k_new = i*m + j;
}while(k_new != k_start);
// if the current value is not the minimum of the cycle, then don't
// perform the cycle
if(abort)
continue;
// otherwise, perform the cycle
k_new = k = k_start;
do
{
swap( data[k_new], temp );
k = k_new;
i = k%n;
j = k/n;
k_new = i*m + j;
}while(k_new != k_start);
swap( data[k_new], temp );
}
}
```
And the result:
![In Place Transpose](/wordpress/wp-content/uploads/2009/07/transpose.jpg)