Transpose a 2D array

Question

How do you efficiently transpose a matrix? Are there libraries for this, or what algorithm would you use?

E.g.:

short src[W*H] = {
  {1,2,3},
  {4,5,6}
};
short dest[W*H];


rotate_90_clockwise(dest,src,W,H); //<-- magic in here, no need for in-place

//dest is now:

{
  {4, 1},
  {5, 2},
  {6, 3}
};

(In my specific case its src array is raw image data, and the destination is a framebuffer, and I'm embedded on ARM on a toolchain that doesn't support assembly)

Answer 1

One very simple solution that works in O(1) is saving an additional boolean for the matrix, saying whether it is 'transposed' or not. Then accessing the array will be made according to this boolean (row/col or col/row).

Of course, it will impede your cache utilization.

So if you have many transpose operations, and few "complete traversals" (which, btw, might also be re-ordered according to the value of the boolean), this is your best choice.