Сортировка слов по частоте в хэш-таблицу с использованием qsort в C

Question

Моя задача - улучшить время выполнения программы, которая сортирует все слова из TXT-файла в хэш-таблицу. Этот тройной вложенными для алгоритма сортировки петли проблема:

// 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++; 
} 

То, что я хотел бы сделать, это использовать QSort(), но я теряюсь, куда я должен начать. Любые предложения помогут, спасибо.

ОБНОВЛЕНИЕ: Я изменил выше фрагмент следующим образом:

// 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++; 
} 

и добавили эту функцию сравнения:

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

структура для h_ptr является:

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

При Я скомпилирую, я получаю эту ошибку:

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) 

Answer 1

Две петли for в обновленном коде создания несортированный массив, сохраняя при этом отслеживать количество элементов в массиве в переменной cnt. Вы должны позвонить qsort после того, как закончились петли for, и передайте cnt в качестве второго аргумента qsort.

Функция сравнения всегда должна следовать прототипу функции, указанному qsort. Плохая практика заключается в определении функции-компаратора, которая требует приведения в качестве четвертого аргумента для qsort. См. wikipedia article для примера того, как написать правильную функцию компаратора.

В вашем случае, первые две строки функции компаратора должны быть

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

Обратите внимание, что я всегда не ставить * с в определений типов. Это источник ваших сообщений об ошибках, вы неправильно учли тот факт, что в вашем коде a и b на самом деле имеют тип указателя на указатель на структуру-HELE.