Rotate square matrix clockwise by 90degrees

Question

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
void nl(void) { //function to print new line
 printf("\n");
}
int** allocate(_size) {
 int** matrix=(int**)malloc(sizeof(int*)*_size);
 for(int i=0;i<_size;i++) {
 matrix[i]=(int*)malloc(sizeof(int)*_size);
 }
 return matrix;
}
void scanMatrix(_matrix,_size)
int** _matrix;
{
 printf("Enter the values: ");
 for(int i=0;i<_size;i++) {
 for(int j=0;j<_size;j++) {
 scanf("%d",&_matrix[i][j]);
 }
 }
}
void printMatrix(_matrix,_size)
int** _matrix;
{
 for(int i=0;i<_size;i++) {
 for(int j=0;j<_size;j++) {
 printf("%d ",_matrix[i][j]);
 }
 nl();
 }
}
void swap(num1,num2)
int* num1;
int* num2;
{
 *num1=*num1+*num2;
 *num2=*num1-*num2;
 *num1=*num1-*num2;
}
void rotateMatrix(_matrix,_size)
int** _matrix;
{
 for(int i=0;i<_size;i++) {
 for(int j=i+1;j<_size;j++) {
 swap(&_matrix[i][j],&_matrix[j][i]);
 }
 }
 for(int i=0;i<_size;i++) {
 for(int j=0;j<_size/2;j++) {
 swap(&_matrix[i][j],&_matrix[i][_size-1-j]);
 }
 }
}
main(argc,argv)
const char** argv;
{
 int size=0;
 printf("Enter the size of the square matrix: ");
 scanf("%d",&size);
 int** matrix=allocate(size);
 scanMatrix(matrix,size);
 printMatrix(matrix,size);
 nl();
 rotateMatrix(matrix,size);
 nl();
 printMatrix(matrix,size);
 return 0;
}

This code doesn't use extra memory and also uses run-time allocation using malloc. However, has a time complexity of O(n^2). How do I further optimise it?

• kesarling: Even Swap doesn't use extra memory. Regarding n, why do you say that n=size^2? Will you please elaborate? :)
• slepic: Btw how do you call the syntax with function argument types defined after the function prototypes? I have never seen this syntax. How do I refer to it?
• kesarling: Just search for Kernighan and Ritchie notation on Google. :) It isn't standard syntax and was used by Ritchie. I use it because I learnt C from first edition of The C programming language. Don't use it if possible :)
• slepic: Well I suppose n Is the number of elements in the matrix. Since the matrix Is square i Believe number of elements Is size^2 where size Is the size of edge of the square Matrix.
• Roland Illig: @slepic anytime you say \$\mathcal O(n)\,ドル you must define what you mean by \$n\$. Otherwise it’s not reliable.

Answer 1

regarding:

void rotateMatrix(_matrix,_size) 

1. do NOT use leading underscores for variable and/or parameter names.
2. a function signature must have the variable types as part of the signature.
3. when compiling, always enable the warnings, then fix those warnings

regarding:

main(argc,argv)

there are two valid signatures for the main() function, the are:

int main( int argc, char *argv[] )
int main( void )

the posted signature is missing the return type and the parameters are missing the needed typing

regarding:

main(argc,argv)
const char** argv;

1. This is an obsolete method of writing a function signature, that was replaced back in the late '80s.
2. some 20+ years ago, the 'default' of a untyped variable and/or function parameter defaulting to int was discarded.

regarding:

void nl(void) { //function to print new line
printf("\n");
}

this function should be deleted. Then when wanting to print a newline, use:

puts( "" );

regarding this kind of statement:

int** matrix=(int**)malloc(sizeof(int*)*_size);

1. in C, the returned type is void* which can be assigned to any pointer. Casting just clutters the code.
2. when calling any of the heap allocation functions: malloc() calloc() and/or realloc(), always check (!=NULL) the returned value to assure the operation was successful. If not successful, then call perror( "malloc failed" ); to inform the user of the problem.

Regarding:

scanf("%d",&size);

when calling any of the scanf() family of functions, always check the returned value (not the parameter values) to assure the operation was successful. Those functions return the number of successful 'input format conversion specifiers'. In the current statement suggest:

if( scanf("%d",&size) != 1 )
{
 fprintf( stderr, "scanf for size failed\n" );
 exit( EXIT_FAILURE );
}

for readability and ease of understanding: Please insert a reasonable space:

1. inside parens
2. inside braces
3. inside brackets
4. after commas
5. after semicolons
6. around C operators

regarding the function: scanMatrix()

1. The posted code fails to keep the user informed of where in the matrix the next number entered will be placed nor when all the numbers have been entered.

Suggest the calls to nl() in main() be moved to the end of the functions: rotateMatrix() and printMatrix()

the posted code has several memory leaks as it fails to pass the pointers to each of the allocated memory areas to free()

• chux: Note: "there are two valid signatures for the main() function," --> true, yet an implementation can have others. "or in some other implementation-defined manner." § 5.1.2.2.1 1
• chux: Minor: Using printf("\n"), puts( "" ) or putchar( '\n' ) will emit the same efficient code with a good compiler. Best to code for clarity than concern about an only potential small linear optimization.
• user3629249: @chux-ReinstateMonica, Only emits the same efficient code if optimization turned up.

Answer 2

has a time complexity of O(n^2).

I think you are incorrectly using "n" as if it is the size of the n×ばつn matrix.

The "n" in O() notation refers to the total size of the input data.

So, for a ×ばつm matrix, the "n" value for complexity would be m².

Your algorithm is O(n).

---

This code doesn't use extra memory

Is there a specific reason for doing the swap trick the way you did rather than simply using the more obvious method with an auto int temp; on the stack?

auto memory is allocated on a stack, so it exists only during the invocation of the function. After that, it can be reused by other functions. Unless a function is called recursively, there's no cumulative problem with using temporary stack space; that's what it's for.

And if an algorithm should ever actually require persistent storage, it would be done using static rather than auto.

---

This is C using the Original K&R C.

The biggest drawback to using that is that you don't get the benefit of typechecking, which was introduced in C89.

The compiler won't notice any problem with this:

swap(&_matrix[i][j],&_matrix[j][i]);
swap(_matrix[i][j],_matrix[j][i]);
swap("me", "you");

but at runtime things will fail.

I hope you are at least using lint on the source to check for such problems.

• Malachi: @RayButterworth could your comment be part of your review? if so, please edit it into your answer appropriately with enough context to explain how it pertains to code in question. Comments are not meant to be used for additional review and could be deleted at any time.
• chux: @d4rk4ng31 The suggested swap here does not use more more memory than the posted code (printMatrix() easily runs much deeper on the stack) so the question remains as to why use this problematic swap. Perhaps one could ask, why think the original code saves memory?
• chux: Ray, Given scanf("%d",&size);, algorithm is O(size*size). I agree the prompt printf("Enter the size of the square matrix: "); does leave room for confusion.
• chux: Hmmm "This is C using the Original K&R C." and apparently newer features too with for(int i=0;i<_size;i++) vs. int i; ... for(i=0;i<_size;i++)
• Ray Butterworth: @chux-ReinstateMonica says "algorithm is O(sizesize)*". Correct. The size of the input is also "sizesize", not simply "size". The "n" in O(n) notation would be the same as n=sizesize. But the original question used "n" as if it represented "size" rather than "size*size". If one triples the "size", nine times as much processing is needed, but the size of the input matrix will also be nine times larger, so the effect is linear, hence it is an O(n) algorithm.

Answer 3

As memory management is one of the question's tags, writing swap that way is NOT the way to go:

• Harder to understand
• Risks overflows
• Is less efficient when looking at the compilation result: https://godbolt.org/z/iBlZ8n

The first thing to change if memory management is a concern is the allocation of the matrix. Allocate it as a continuous chunk of memory, without extra pointers.

• chux: UV for the good memory squeezing idea. Even remaining with the extra level int **, the allocation of pointers and ints could be done in one step, saving the allocation overhead. Its somewhat ugly code to do that, but does save real memory over OP's _size + 1 allocations