сортировки массива структур в с

Question

я иметь структуру:

typedef struct book{ 
    double rating; 
    double price; 
    double relevance; 
    int ID; 
}B; 

массив

list* B; 

и файл из них так что читайте в файлах с этим

int read_file(char* infile, int N) 
{ 
    int c; 
    if((fp=fopen(infile, "rb"))) 
    { 
     fscanf(fp, "%*s\t%*s\t%*s\t%*s\n"); 
     c=0; 
     while((!feof(fp))&&(c<N)) 
    { 
     fscanf(fp, "%lf\t%lf\t%lf\t%d\n", &list[c].rating, &list[c].price, &list[c].relevance, &list[c].ID); 
     c++; 
    } 

fclose(fp);  
    } 
    else 
    { 
     fprintf(stderr,"%s did not open. Exiting.\n",infile); 
     exit(-1); 
    } 
    return(c); 
} 

и метод сравнения

int comp_on_price(const void *a, const void *b) 
{ 

    if ((*(B *)a).price < (*(B *)b).price) 
    return 1; 
    else if ((*(B *)a).price > (*(B *)b).price) 
    return -1; 
    else 
    return 0; 

} 

Я хотел бы стабильный сорт с NLog (п) возможно сливаться сортировать по порядку низкой Prie к высшему

мне нужно только 20 низкие цены.

Как бы это реализовать, используя мой метод сравнения?

благодаря

Answer 1

Я, наконец, сделал это, используя сортировку счета, которая потребовала более 100 строк кода в c.

я тогда сделал это в одной строке в сценарии оболочки

сортировать -nk 2,2 -s Wodehouse.txt | sort -rnk 3,3 -s | sort -rnk 1,1 -s | head -20

Answer 2

qsort является вашим другом :). (в то время как в худшем случае это не Nlog (N), трудно сделать что-либо быстрее)

Answer 3

Функция, которую вы хотите использовать, - qsort. C поставляется с совершенно приемлемым типом, который делает точно, что вам кажется.

qsort сам по себе не является стабильным родом (ну, это может быть для данной реализации, но стандарт не гарантирует его), но это может быть сделано в один с каким-то обманом. Я сделал это раньше, добавив указатель на элементы массива, который изначально заполнен адресом самого элемента (или, возможно, здесь будет увеличиваться целочисленное значение, когда вы читаете файл).

Тогда вы можете использовать это как второстепенный ключ, который обеспечивает сохранение элементов с одним и тем же основным ключом.

Если вы не хотите перейти к проблеме изменения структур, Алгоритмист - хорошее место для get code. Я, как правило, предпочитаю небольшие модификации для повторных реализаций.

Чтобы на самом деле сделать его стабильным, изменить свою структуру:

typedef struct book { 
    double rating; 
    double price; 
    double relevance; 
    int ID; 
    int seq;         // Added to store sequence number. 
} B; 

и изменить свой файл код для чтения в:

fscanf(fp, "%lf\t%lf\t%lf\t%d\n", ... 
list[c].seq = c;       // Yes, just add this line. 
c++; 

тогда ваша функция сравнения становится чем-то вроде:

int comp_on_price(const void *a, const void *b) { 
    B *aa = (B*)a; 
    B *bb = (B*)b; 

    if (aa->price < bb->price) 
     return 1; 
    if (aa->price > bb->price) 
     return -1; 
    return (aa->seq < bb->seq) ? 1 : -1; // Cannot compare equal. 
} 

Answer 4

Поскольку вы упомянули C, а не C++, я бы сказал, что вы решили реализовать свою собственную версию что-то похожее на qsort().

Посмотрите, как определяется компаратор для qsort. Вам нужно было бы определить что-то подобное для себя? Для фактической сортировки вам потребуется реализовать собственную версию StableSort() с нуля.

Answer 5

Я хотел бы стабильный сорт с NLog (п), возможно, сортировка слиянием в порядке самой низкой до самой высокой Prie

мне нужно только 20 низкие цены.

Тогда вы можете сделать это в O (n) раз. Вы можете найти первые 20 значений в O (N) времени, а затем сортировать их O (1).

See here for the STL C++ library version

Annotated Python implementation here

Answer 6

Это просто небольшие изменения в функции comparizon, чтобы сделать библиотеку QSort стабильной. Смотрите ссылку here

что-то вроде ниже, должны сделать трюк (непроверенный, быть осторожным):

int comp_on_price(const void *a, const void *b) 
{ 
    if ((*(B *)a).price < (*(B *)b).price) 
     return 1; 
    else if ((*(B *)a).price > (*(B *)b).price) 
     return -1; 
    else 
     // if zero order by addresses 
     return a-b; 
} 

Это будет работать, если вы можете гарантировать и Ь в том же адресном пространстве (два указателя в том же массив) и что при каждом сравнении обеспечивается более полное упорядочение массива, адреса нижних структур будут становиться еще медленнее. Это справедливо для сортов пузырьков или подобных. Это также будет работать для тривиальной реализации QucikSort (чего нет qsort). Однако для других алгоритмов или любого алгоритма, использующего дополнительное адресное пространство для временного хранения (возможно, для оптимизации), это свойство не будет истинным.

Если вы сортируете какой-либо уникальный идентификатор в сравниваемых элементах (в текущем примере, который, вероятно, верен для идентификатора поля), другим способом сделать стабилизацию сортировки будет сравнение этих элементов. Вы также можете добавить такой уникальный ключ в новое поле для этой цели, но поскольку он использует больше памяти, вы должны рассмотреть третий вариант, описанный ниже, перед тем как это сделать.

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

Функция сравнения будет что-то вроде:

int comp_on_price(const void *a, const void *b) 
{ 
    if ((*(B **)a)->price < (*(B **)b)->price) 
     return 1; 
    else if ((*(B **)a)->price > (*(B **)b)->price) 
     return -1; 
    else 
     // if zero, order by addresses 
     return *(B **)a-*(B **)b; 
} 

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

Недостатки в том, что требуется некоторая память и доступ к элементам несколько медленнее (один уровень косвенности больше).

Answer 7

Вам не нужно все qsort. Просто создайте пустой массив B * для 20 наименьших записей, скопируйте первые < = 20 записей и qsort их, если их больше, чем 20, тогда, когда вы перебираете свои элементы, сравнивайте их с самыми высокими в первых 20: if больше, затем продолжайте еще сравнить с предыдущим самым высоким и т. д. назад к самому низкому, а затем сдвиньте другие указатели, чтобы освободить место для следующей записи в малом 20. Вам нужно детерминированное сравнение - послушайте paxdiablo на этом фронте: добавьте номер входной записи или что-то, чтобы отличить записи.