【C言語】ファイルでのソート方法について

ファイルの大量データ（構造体をバイナリで書き込んだ）をソートする時（構造体のメンバの1つをキーとして）に用いるソート法で高速にできるソート法はなんでしょうか？
選択法でやっているのですが遅いもので・・・・
配列ではなくてファイルに対して高速なソート法をご教示いただきたく。
ファイル全てを読んでからソートしないと厳しいでしょうか？

まだまだｃ言語初心者ですが、なにかアドバイスをよろしくお願い致します。

No.3 ベストアンサー 回答者： mtaka2 回答日時： 2008/06/09 17:09

全データをオンメモリに持てないのでしたら、マージソートでしょう。

ただし、メモリに読めるならメモリ上で実行した方が速いので、
「ファイルから読めるだけ読んで、メモリ上ではクイックソートなどの高速なソート手段を使」って、「ソートされたデータ」群を生成し、
「ソート済データ列」に対しマージソートを実行って感じで。

例えば10000件のデータをソートするのに1000件しかメモリ上に乗らないなら、1000件ずつ読み込んで「ソートされた1000件のデータ列×10本」を作り、それをマージソートでマージして「ソートされた10000件のデータ列」を作る。

この回答へのお礼

メモリ上でソートしてみたいと思います。
アドバイスありがとうございました。

お礼日時：2008/06/10 09:19

No.2 回答者： hidebun 回答日時： 2008/06/09 16:53

”ファイル内の構造体のメンバの1つをキーとして用いる”というルールがあるなら、ファイル内からキーを取り出してからソートしなきゃいけないと思うけど。

で、基本選択法がボトルネックではなくて、ファイルの読み込みがネックなんですか？

ファイルの読み込みがネックなら、環境がWindowsかUnixかわかりませんが、メモリマップドファイルで必要なところのみ参照すると速くなるかも。

No.1 回答者： nak777r 回答日時： 2008/06/09 16:50

どのやり方でやるにしても、ファイルにアクセスする時間が一番かかります

指定レコードを２つファイルから読んで、そのレコードを比較、入替えが発生したら
ファイルに書いて、なんて事をしているのであれば、そのつどファイルアクセスが
発生するので大変時間がかかります

逆に、ファイルの内容全てをメモリに読込んで、メモリの中でソート処理をして
メモリの内容全てをファイルに書き込むという方法を取れば、どんなソートでも
早いです

１．ファイルのサイズを求める
２．ファイルサイズ分のメモリ確保
３．ファイル全体を読込む
４．メモリの先頭に構造体のポインタを割当てて構造体の配列として、
　　ソートの処理を行う
　　（４バイト境界の問題があるかも）
５．既存ファイル削除後、新規ファイルとしてファイルを作成し
　　メモリの情報を全て書き込む
６．メモリの開放

こんな手順でやれば、たいがい早いです
ファイルサイズが膨大な場合、データベースを使用する事を提案します

この回答へのお礼

ファイルアクセスを減らしながらもソートするのは難しそうですね。

お礼日時：2008/06/10 09:15