# Quicksort comparison

1. Jun 30, 2008

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. Jun 30, 2008

### Staff: Mentor

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