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

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 (n), возможно, сортировка слиянием по порядку от младшего к старшему

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

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

спасибо

Answer 1

Я бы хотел стабильную сортировку по времени nlog (n), возможно, сортировку слиянием в порядке убывания от младшего до максимального

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

Здесь вы найдете версию библиотеки STL C ++

Аннотированная реализация Python здесь

Answer 2

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

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

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

Answer 3

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

Answer 4

Это просто небольшие изменения в вашей функции сравнения, чтобы сделать библиотеку 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 a-b;
}

Это будет работать, если вы можете гарантировать, что 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 5

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

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

Answer 6

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

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

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

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

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

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 7

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