qsort() performance issue

Question

I'm successfully sorting an array of structs, where each struct only contains a char string. My problem however, is that for a struct array of approx. 900,000 elements, qsort is taking alot longer than I expect (qsort takes about 2 mins to sort this array); leading me to think there is something I am overlooking here. The sorting is a trivial part of the assignment I am working on, and alone completely over passes the time limit I have for my program.

Below are the relevant parts of my code:

struct WordsArray //Just a struct thath holds a *char
{
    char word[25];
};

Compare function passed into qsort:

int cmpfunc(const void *a, const void *b)
{
    const struct WordsArray *a1;
    a1 = (WordsArray*)malloc(sizeof(WordsArray));
    const struct WordsArray *b1;
    b1 = (WordsArray*)malloc(sizeof(WordsArray));
    a1 = (struct WordsArray*)a;
    b1 = (struct WordsArray*)b;

    return strcmp(a1->word, b1->word);
}

My call to qsort:

WordsArray *AllWordsArray;
AllWordsList = (WordsArray*)malloc(sizeof(WordsArray)*ListSize);
qsort(AllWordsList->word, ListSize, sizeof(struct WordsArray), cmpfunc);

Thanks for your input.

You're allocating memory inside your comparator function. It is unnecessary, slows your program down and causes a memory leak, since you never free it. Look at the comparator and fix it. — Alex Reynolds

Sergey Kalinichenko Sergey Kalinichenko · Accepted Answer · 2015-04-14T16:18:16

The problem is with your cmpfunc's implementation: it leaks memory faster than a fire hydrant!

You are allocating (WordsArray*) pointers only to write over them on the very next line, creating a memory leak in the process. All you need to do is removing mallocs:

int cmpfunc(const void *a, const void *b) {
    const struct WordsArray *a1 = (struct WordsArray*)a;
    const struct WordsArray *b1 = (struct WordsArray*)b;
    return strcmp(a1->word, b1->word);
}

qsort() performance issue

1 Answers