Search code examples
c++arraysalgorithmrotationin-place

Rotate 2D rectangular array in-place

I have an non-square array like this:

const int dim1 = 3, dim2 = 4;
int array[12] = { 1, 2, 3, 
                  4, 5, 6,
                  7, 8, 9,
                 10,11,12};

and I need to convert it to:

{3,6,9,12,
 2,5,8,11,
 1,4,7,10}

that is, rotate/shuffle it counter-clockwise (or clockwise, the algorithm should be similiar).

The algorithm should use a minimal amount of space. I have to rotate an image in an extremely memory-constrained environment, so the less space the better. Speed is not as big an issue.

Solution

  • You can transpose the matrix in-place (see http://en.wikipedia.org/wiki/In-place_matrix_transposition) and then reverse the rows which is trivial.