Cの構造体の配列をソートする

StackOverflow https://stackoverflow.com/questions/4245546

  •  27-09-2019
  •  | 
  •  

質問

私には構造があります:

  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 件だけが必要です。

比較メソッドを使用してこれを実装するにはどうすればよいですか?

ありがとう

役に立ちましたか？

解決 7

私は最終的にそれがCのコードの100行を引き継いだカウンティングソートを使用してこれをしました。

私は、シェルスクリプトで1行でそれをやった。

ソート-nk 2,2 -s Wodehouse.txt |ソート3,3 -sを-rnk |ソート-rnk 1,1 -s |頭-20

他のヒント

  

は、私は時間が、おそらく最高

に最低PRIEの順にソートマージソートnlog（n）を有する安定したいです      

私は20、最低価格を必要とします。

そして、あなたはO（n）の時間でこれを行うことができます。その後、並べ替え、それらのO（1）O（N）時間の最初の20個の値を見つけることができます。

STLのCについてはこちらを参照してください++ライブラリのバージョンの

ここを

のqsort にあなたの友達です:)。 （それは最悪の場合にはNlog（N）ではないのですが、それはより速く何かを行うことは困難です）。

C++ ではなく C について言及したため、次のようなものを独自のバージョンで実装することを検討すると思います。 qsort().

qsort のコンパレータがどのように定義されているかを見てください。同様のものを自分で定義する必要があるでしょうか?実際の並べ替えを行うには、独自のバージョンの StableSort() を最初から実装する必要があります。

使いたい機能は、 qsort. 。C には完全に許容可能なソートが付属しています。 その通り 必要と思われるもの。

qsort それ自体は安定した種類ではありません (まあ、それは 5月 特定の実装向けのものですが、標準はそれを保証していません)、しかし、いくつかのトリックを使えばそれを 1 つにすることができます。私は以前、配列要素へのポインタを追加することでこれを実行しました。このポインタには、最初に要素自体のアドレスが設定されます (または、ここではおそらくファイルを読み込むにつれて増加する整数値が設定されます)。

その後、それをマイナー キーとして使用することができ、同じメジャー キーを持つ要素が確実に順番に保持されます。

もし、あんたが しないでください わざわざ構造を変更したい場合は、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.
}

はあなたはのqsortすべてにする必要はありません。あなたの要素についてのあなた反復は、最初の20で最高にそれらを比較すると、その後20以上がある場合だけで、それらを、空のB * 20の最低レコードの配列を作成し、そこに最初の<= 20件のレコードをコピーしてのqsortます。ifもっとそして低20であなたの次のエントリのためのスペースを作るために他のポインタをシフトし、その後、他の最低の次に高いなどとの比較背を続けます。あなたは決定論的比較が必要なのか - その前面にpaxdiabloを聞く：分化レコードを入力レコード番号または何かを追加

これは、ライブラリのqsortの安定を作るためにあなたのcomparizon機能にちょうどわずかな変化です。リンクを参照してください。ここを

以下のようなものは、トリックを（未テスト、慎重で）行う必要があります 

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が同じアドレス空間（同一アレイ内の2つのポインタ）であり、すべての比較は、配列のより大きな全体的な順序付けを与えることを保証することができれば、下の構造体のアドレスがさらに遅くなる傾向があります動作します。これは、バブルソートまたは類似についても同様です。それはまた、（qソートではありません）QucikSortの些細な実施のために働くだろう。しかし他のアルゴリズム、または（多分最適化の目的のために）一時的に格納するための追加のアドレス空間を使用して、任意のアルゴリズムのために、このプロパティはtrueになりません。

ソート（フィールドIDのために、おそらく真実である現在の例では）比較項目に任意の一意の識別子が含まれているどのような場合には、

、ソートの安定を作るための別の方法は、これらの項目を比較することであろう。あなたはまた、その目的のための新たな分野でそのようなユニークなキーを追加することができますが、それはより多くのメモリを使用して、あなたは番目のオプションは、それを行う前に、以下の説明を検討する必要があります。

私の好ましい方法はまだない構造の直接ソート配列が、実際の構造アイテムへのポインタの配列の並べ替えを行い、第三ものであろう。これは、いくつかの優れた特性を有します。まず、構造体の配列を比較することができ、それは変更されません、それはソートの安定を行いますように指摘しています。

比較関数は次のようになります 

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

他の優れた特性が、それが仕分けしながら、周りの構造を移動しないことで、それだけで動くポインタを必要とし、それは時間を節約することができます。また、そのようないくつかのポインタ配列を維持し、その同時に、配列項目にいくつかの注文のアクセスを許可することができます。

欠点がいくつかのメモリを取り、アイテムへのアクセスは、（複数間接のいずれかのレベル）わずかに遅いことである。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top