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?

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()

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×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.

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.