11
\$\begingroup\$

I wrote an isPermute method. Can I get some tips and advice on better coding style?

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool isPermute(char*, char*);
char* sort(char*);

int main(int argv, char **argc)
{
  printf("%s and %s are %spermutations of each other. \n", argc[1], argc[2], isPermute(argc[1], argc[2]) ? 
    "" : "not ");

  return 0;
}

bool isPermute(char* s1, char* s2)
{

  int size1 = strlen(s1);
  int size2 = strlen(s2);

  //default cases
  if((size1 != size2) || (size1 == 0) || (size2==0))
    return false;  

  if(strcmp(sort(s1), sort(s2)))
    return false;

  else
    return true;
}

char* sort(char* str1)
{
  int d=0, size = strlen(str1);
  char character;
  char *original = str1;

  char *result = (char *)malloc(size);

  for ( character = 'a' ; character <= 'z' ; character++ )
  {
     int i;
     for ( i = 0 ; i < size ; i++ )
     {
        if ( str1[i] == character )
        {
           result[d] = str1[i];
           d++;
        }
     }
     str1 = original;
  }
  return result;
}
\$\endgroup\$
  • 5
    \$\begingroup\$ isn't it normally int argc, char** argv? as in argcount, and arg value? \$\endgroup\$ – Dannnno Dec 28 '15 at 23:26
  • 1
    \$\begingroup\$ If your goal is not exercising in sorting algorithms I'd suggest to use qsort, a standard library sorting function, for sorting characters in a string in O(n log n) time. Or you may prepare two arrays of character counters (constant time), scan both strings to count characters' repetitions (linear time) and compare corresponding counters (constant time)... \$\endgroup\$ – CiaPan Dec 28 '15 at 23:29
  • 2
    \$\begingroup\$ Your main arguments should be (int argc, char **argv) or (int argc char *argv[]). You switched the two variable names. Argc means arguments count. Argv means arguments vector \$\endgroup\$ – Zorgatone Dec 28 '15 at 23:35
  • \$\begingroup\$ @CiaPan qosrtis not O(n log n). It has a O(n^2) worst case behavior. \$\endgroup\$ – Federico Poloni Dec 29 '15 at 14:24
  • \$\begingroup\$ @FedericoPoloni The worst case, yes. But the average is (n × lg n). And the code presented is (26 × n), which – although linear – is greater than the former for string length n up to 64MB. Even if we suppose the constant, corresponding to the single iteration cost for qsort is thousand times that of linear scan, qsort will still be faster (except the rare worst case) for strings up to about 60 thousand characters. \$\endgroup\$ – CiaPan Dec 29 '15 at 16:39
12
\$\begingroup\$

First off:

bool isPermute(char*, char*);
char* sort(char*);

You could just move the function implementation over the main method, avoiding to have these declarations; however, that isn't really a big deal.

The convention for int main isn't:

int main(int argv, char **argc)

It normally is the opposite: argc is for the arg count and argv is for the arguments passed to the program.

So it really should be:

int main(int argc, char **argv)

Next:

printf("%s and %s are %spermutations of each other. \n", argc[1], argc[2], 
    isPermute(argc[1], argc[2]) ? "" : "not ");

You never checked if the program was actually passed two parameters, and so instead it should be (argc is the arg count from now on, and argv is the arguments)

if(argc == 3) 
{
    printf("%s and %s are %spermutations of each other. \n", argv[1], argv[2], 
        isPermute(argv[1], argv[2]) ? "" : "not ");
}
else 
{
    printf("Incorrect amount of parameters passed!\n");
    return -1;
}

The following:

if(strcmp(sort(s1), sort(s2)))
    return false;
else
    return true;

can be trimmed down to be just:

return !strcmp(sort(s1), sort(s2));

The following:

char *result = (char *)malloc(size);

You don't need to have the explicit cast (char *) as malloc returns a void*, so it can just be

char *result = malloc(size); 

Which doesn't detract from clarity in any real way.

Also, I've noticed that you are declaring variables for the for loops outside the loop, even though that isn't necessary (unless you are using C89, in which case, ignore this)

So this:

for ( character = 'a' ; character <= 'z' ; character++ )
{
     ...
}

would become

for (char character = 'a'; character <= 'z'; character++)
{
    ...
}

The same thing essentially applies for the other for loop.

for ( i = 0 ; i < size ; i++ )
{ 
    ...
}

would become

for (int i = 0; i < size; i++)
{
    ...
}
\$\endgroup\$
  • 5
    \$\begingroup\$ Welcome to Code Review! GOod job on your first answer. \$\endgroup\$ – SirPython Dec 29 '15 at 0:08
  • \$\begingroup\$ Hello, thank you so much for your answer! I took all of the suggestions. I am using C89 cause when i declare it inside, it gives me an error saying it's only available C99 or C11. So first question is, how do I change it to C99? Is it my machine? Also, why is the argc count = 3 even though I enter only 2? Is there an implicit input also? \$\endgroup\$ – Jonathan Dec 29 '15 at 2:44
  • 1
    \$\begingroup\$ @JonathanSmit The argc count is 3, because the program name is the first parameter: argv[0]. Are you using GCC? If so then just add the -std=c99 flag or -std=gnu99 flag (which enables some GNU specific stuff in addition to the c99 stuff) \$\endgroup\$ – mmk Dec 29 '15 at 2:49
  • 1
    \$\begingroup\$ @JonathanSmit That's generally a compiler setting -- I'm not sure the exact syntax for your compiler, but the man pages/help docs probably have it. \$\endgroup\$ – Nic Hartley Dec 29 '15 at 2:49
5
\$\begingroup\$

Corner case

This condition:

if((size1 != size2) || (size1 == 0) || (size2==0))
  return false;

Misses the case where both strings are empty, as the empty string is a permutation of the empty string.

Boolean return anti-pattern

  if(strcmp(sort(s1), sort(s2)))
    return false;

  else
    return true;

Becomes:

return ! strcmp(sort(s1), sort(s2))

It does the same, but it's shorter & simpler.

\$\endgroup\$
5
\$\begingroup\$

Memory issues

The following memory region is allocated but never freed and the size of allocated memory region is missing the terminating zero character.

     char *result = (char *)malloc(size);

The terminating zero charcter is not written to result but it is required for the result string but is required for the strcmp() function to work correctly.

Algorithm

It works only on lower case characters. It produces wrong results when other characters are used. This should be either mentioned in the documentation (if intended), maybe checked at runtime or corrected.

Extending the algorithm to all characters except zero increases the runtime due to the nested loops from O(size * 26) to O(size * 255) which might be undesired for small strings. Have a look at https://stackoverflow.com/questions/33294426/sort-string-by-character-in-c-programming for a character sorting using quicksort.

Documentation

The sort() and isPermute() functions are missing entire documentation about what they do, the parameter and its return values. Something like

    /** sort() takes a zero terminated character string and returns a
    string of the same size with contents sorted lexicographically.
    The returned string has to be deallocated by the caller using free(). */
\$\endgroup\$
  • \$\begingroup\$ Hello, to free the malloced variable, I am doing something like this. Any feedback? char sortS1[size1]; char sortS2[size2]; char* temp1 = sort(s1); char* temp2 = sort(s2); strcpy(sortS1, temp1); strcpy(sortS2, temp2); free(temp1); free(temp2); return !strcmp(sortS1, sortS2); \$\endgroup\$ – Jonathan Dec 31 '15 at 22:02
2
\$\begingroup\$

these two lines cause the compiler to output warnings about conversion to different types because strlen() returns a size_t, not a int

  int size1 = strlen(s1);
  int size2 = strlen(s2);

suggest using:

  size_t size1 = strlen(s1);
  size_t size2 = strlen(s2);

for readability, follow the axiom: only one statement per line and (at most) one variable declaration per statement

SO this line:

int d=0, size = strlen(str1);

becomes:

int d=0;
size_t size = strlen(str1); // remember strlen() returns a 'size_t` not an 'int'

after applying the above changes, then these lines:

int i;
for ( i = 0 ; i < size ; i++ )

become

 for ( size_t i = 0 ; i < size ; i++ )

Always check the first parameter to main() to assure that the command line had the correct number of parameters before accessing anything beyond (in your case) argc[0] And when the command line did not contain the correct number of parameters, the output, on stderr, via fprintf(stderr, ...) how the program should be invoked

Note: by convention, the main signature is written like this:

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

where argc is the COUNT of number of command line parameters

where argv[] is a VECTOR of pointers to character strings of the parameters

\$\endgroup\$
2
\$\begingroup\$

This is not about a coding style but rather about an efficient algorithm: instead of sorting characters in strings you might just count them.

Prepare an array of integers, indexed with characters. Fill it with zeros. Scan a string, incrementing a counter for each character found. Then scan the other string, but this time decrement counters.

The two strings are anagrams (permutations) of each other iff all the counters are zero.

\$\endgroup\$

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.