Archive for July, 2009

In-Place Matrix Transpose

Posted by cheshirekow in C++ Discoveries and Notes, Programming on July 28, 2009

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 O(n^2) where n is the size of the matrix n = rows times columns

Edit: No longer arbitrarily repeating cycles ( was leading to identity operation, duh! ).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

template <typename T>
void CMatrix<T>::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<T>( data[k_new], temp );
 
            k       = k_new;
            i       = k%n;
            j       = k/n;
            k_new   = i*m + j;
        }while(k_new != k_start);
 
        swap<T>( data[k_new], temp );
    }
}

And the result:

In Place Transpose

In Place Transpose

1 Comment