4
\$\begingroup\$
#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?

\$\endgroup\$
  • 1
    \$\begingroup\$ Even Swap doesn't use extra memory. Regarding n, why do you say that n=size^2? Will you please elaborate? :) \$\endgroup\$ – d4rk4ng31 Jan 1 at 13:06
  • 1
    \$\begingroup\$ 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? \$\endgroup\$ – slepic Jan 1 at 13:06
  • 1
    \$\begingroup\$ 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 :) \$\endgroup\$ – d4rk4ng31 Jan 1 at 13:08
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ – slepic Jan 1 at 13:08
  • 3
    \$\begingroup\$ @slepic anytime you say \$\mathcal O(n)\$, you must define what you mean by \$n\$. Otherwise it’s not reliable. \$\endgroup\$ – Roland Illig Jan 1 at 14:45
3
\$\begingroup\$

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

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ 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 \$\endgroup\$ – chux - Reinstate Monica Jan 4 at 11:14
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ – chux - Reinstate Monica Jan 4 at 11:24
  • \$\begingroup\$ @chux-ReinstateMonica, Only emits the same efficient code if optimization turned up. \$\endgroup\$ – user3629249 Jan 14 at 3:17
5
\$\begingroup\$

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

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.

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Malachi Jan 2 at 17:02
  • 1
    \$\begingroup\$ @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? \$\endgroup\$ – chux - Reinstate Monica Jan 4 at 11:32
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – chux - Reinstate Monica Jan 4 at 11:41
  • 1
    \$\begingroup\$ 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++) \$\endgroup\$ – chux - Reinstate Monica Jan 4 at 11:55
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Ray Butterworth Jan 4 at 15:26
3
\$\begingroup\$

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

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.

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ 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 \$\endgroup\$ – chux - Reinstate Monica Jan 4 at 12:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.