Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Quicksort comparison

  1. Jun 30, 2008 #1
    typedef struct Emp
    {
    unsigned char lname[MaxName + 1]; /* + 1 for '\0' */
    unsigned char fname[MaxName + 1];
    unsigned int id;
    unsigned char dept;
    bool married;
    } Emp;

    int comp1(const void* item1, const void* item2)
    {
    const Emp* emp1 = (const Emp*) item1; //emp1 points to Emp
    const Emp* emp2 = (const Emp*) item2;
    unsigned char buff1[BuffSize];
    unsigned char buff2[BuffSize];

    strcpy(buff1, emp1->lname);
    strcat(buff1, emp1->fname);
    strcpy(buff2, emp2->lname);
    strcat(buff2, emp2->fname);

    return strcmp(buff1, buff2);
    }

    int comp2(const void* item1, const void* item2)
    {
    const Emp** emp1 = (const Emp**) item1; // pointer to pointer to Emp
    const Emp** emp2 = (const Emp**) item2;
    unsigned char buff1[BuffSize];
    unsigned char buff2[BuffSize];
    strcpy(buff1, (*emp1)->lname);
    strcat(buff1, (*emp1)->fname);
    strcpy(buff2, (*emp2)->lname);
    strcat(buff2, (*emp2)->fname);
    return strcmp(buff1, buff2);
    }

    /* 1st qsort: better or worse approach than 2nd? why? emps here is an array*/
    qsort(emps, n, sizeof(Emp), comp1);

    /* 2nd qsort: better or worse approach than 1st? why?
    Emp* emps_a[6] */
    qsort(emps_a, n, sizeof(Emp*), comp2);




    Based on the above code, which is the better quicksort and why?

    thanks, this really has me in a bind....:(
     
  2. jcsd
  3. Jun 30, 2008 #2

    jim mcnamara

    User Avatar
    Science Advisor
    Gold Member

    how about
    Code (Text):

    int compar(const void *A, const void *B)
    {
         const char *a=(const char *)A;
         const char *b=(const char *)B;
         int retval=strcmp(a,b);
         if(!retval)
         {
               Emp *a1=(Emp *)A;
               Emp *b1=(Emp *)B;
               retval=strcmp(a1->fname, b1->fname);
          }
         return retval;
    }
     
    or just
    Code (Text):

    int compar1(const void *A, const void *B)
    {
         return memcmp(A, B, MaxName + 2);
    }
     
    The last one will work ONLY if you don't use strcpy to place values into those strings, and they are initialized to \0 for the full length using memset before they get a new value.

    To answer your question - use a profiler on your code - test your qsort against say 20K records and either time the process or use a profiler. But the answer to your implied question is that both are probably slower than something less involved. Change your compare algorithms. Those above are possible starting points
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?