CODEWITHSUNDEEP
cquicksortqsort
Shannon
Shannon

Reputation: 119

Sort words by frequency into hash table using qsort in C

My task is to improve the runtime of a program that sorts all words from a .txt file into a hash table. This triple-nested for loop sorting algorithm is the problem:

// Sort hash table elements and save as pointers in 'array'
for (i = 0; i < tsize; i++)
   for (ele = htable[i]; ele != NULL; ele = ele->next) {
    if (ele->freq == 1)
    scnt++;

    for (j = cnt; j > 0 && ele->freq > array[j-1]->freq; j--)
      array[j] = array[j-1];

    array[j] = ele;
    cnt++;
}

What I would like to do is use qsort(), but I am lost as to where I should begin. Any suggestions will help, thank you.

UPDATE: I have altered the above snippet as follows:

// Sort hash table elements and save as pointers in 'array'
for (i = 0; i < tsize; i++)
   for (ele = htable[i]; ele != NULL; ele = ele->next) {
    if (ele->freq == 1)
    scnt++;

    array[cnt] = ele;
    qsort(array, tsize, sizeof(h_ptr), (int (*) (const void *, const void *))compare_ele);
    cnt++;
}

and added this comparison function:

// Compare function for qsort
int compare_ele (h_ptr *a, h_ptr *b)
{
    if (a->freq < b->freq)
        return + 1;
    if (a->freq > b->freq)
        return - 1;
    return 0;
}

the structure for h_ptr is:

typedef struct HELE {
    char *word;
    int freq;
    struct HELE *next;
} h_rec, *h_ptr;

When I compile, I receive this error:

analysis.c: In function ‘compare_ele’:
analysis.c:137:10: error: request for member ‘freq’ in something not a structure or union
 if (a->freq < b->freq)
      ^
analysis.c:137:20: error: request for member ‘freq’ in something not a structure or union
 if (a->freq < b->freq)
                ^
analysis.c:139:10: error: request for member ‘freq’ in something not a structure or union
 if (a->freq > b->freq)
      ^
analysis.c:139:20: error: request for member ‘freq’ in something not a structure or union
 if (a->freq > b->freq)

Upvotes: 0

Views: 1151

Answers (1)

user3386109
user3386109

Reputation: 34839

The two for loops in the updated code are creating an unsorted array, while keeping track of the number of items in the array in the variable cnt. You should call qsort after those for loops are finished, and pass cnt as the second argument to qsort.

The comparison function should always follow the function prototype specified by qsort. It is bad practice to define a comparator function that requires a cast when used as the fourth argument to qsort. See the wikipedia article for an example of how to write a proper comparator function.

In your case, the first two lines of the comparator function should be

h_rec *a = *(const h_rec **)p;
h_rec *b = *(const h_rec **)q;

Note that I always avoid putting *s in typedefs. That is the source of your error messages, you haven't properly accounted for the fact that in your code, a and b are in fact of type pointer-to-pointer-to-struct-HELE.

Upvotes: 1

Related Questions