Wednesday, February 23, 2011

WAP for Square Matrix Rotation by 90 Degree

Method 1 (Using auxiliary Space of matrix size)

void rotate (Matrix m)
{
Matrix temp;
for(int i=0;i for(int j=0;j temp[i][j]=m[SIZE-j-1][i];

for(int i=0;i for(int j=0;j m[i][j]= temp [i][j];

}

void print (Matrix a)
{
for(int i=0;i {
for(int j=0;j cout< cout< }
cout<

}
This is the before and after output
/*Original square matrix:
11 22 33
44 55 66
77 88 99

Matrix now rotated 90
77 44 11
88 55 22
99 66 33*/

Time Complexity O(m*n)
Space Complexity O(n)




2nd Method In Place Matrix Rotation (Will Work Only For Square Matrix)

void rotate_matrix_90degree(int **m, int n)
{
int i, j;

// first mirror the matrix along the diagonal line.
for (i = 0; i < n; i++)
{
for (j = i + 1; j < n; j++)
{
int tmp = m[i][j];
m[i][j] = m[j][i];
m[j][i] = tmp;
}
}

// mirror the matrix horizontally. for Left Rotation
// and mirror the matrix vertically for right rotation

for (i = 0; i < n / 2; i++)
{
for (j = 0; j < n; j++)
{
int tmp = m[j][i];
m[j][i] = m[j][n - i - 1];
m[j][n - i - 1] = tmp;
}
}
}

Time Complexity O(m*n)
Space Complexity O(1)

Please write comment if you find any thing wrong in this code or anything
missing

1 comment :

Unknown said...

http://codepad.org/NvE2lNPP