Вопрос о производительности qsort()

Question

Я успешно сортирую массив структур, где каждая структура содержит только строку символов. Моя проблема однако заключается в том, что для массива struct ок. 900 000 элементов, qsort занимает гораздо больше времени, чем я ожидаю (qsort занимает около 2 минут, чтобы отсортировать этот массив); заставив меня подумать, что я кое-что упускаю из виду. Сортировка представляет собой тривиальную часть задания, над которым я работаю, и только один из них полностью соответствует сроку, который у меня есть для моей программы.

Ниже приведены соответствующие части моего кода:

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

функция сравнения переходила в 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); 
} 

Мой призыв к QSort:

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

Спасибо за ваш вклад.

Answer 1

Проблема с вашей реализацией cmpfunc: она утечки памяти быстрее, чем пожарный гидрант!

Вы назначаете указатели (WordsArray*) только для того, чтобы писать над ними на самой следующей строке, создавая утечку памяти в процессе. Все, что вам нужно сделать, это удалить malloc s:

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); 
}