0

大学の課題にマージソートを使用して、データベースの外部ソーティングアルゴリズムを（Cで）実装しようとしています。使用可能なメモリはbuffSizeブロックです。このリンクはとても役に立ちました：

http://web.eecs.utk.edu/~huangj/CS302S04/notes/external-sorting2.html

しかし、私の問題は、アルゴリズムのフェーズ1の擬似コードのこの行に関するものです。

sort array a using an in-memory algorithm like quicksort

buffSize自分のスペース以外のメモリを使用する権利がないためa、リンクの配列を割り当てることができない場合、それらのブロックに含まれているレコードを並べ替える（そして一時的な実行ファイルに保存する）にはどうすればよいですか？ 、メモリ内の並べ替え手順（クイックソートなど）を使用します。その場合の私のレコードは、連続した配列ではなく、連続していないメモリに配置されたブロックにあり、qsortを直接適用することはできません。ヒントはありますか？

4

1 に答える 1

2

外部ソートの一般的なアプローチは次のとおりです。

  1. 配列メモリに収まる限り多くのデータを読み取ります。
  2. 並べ替えます。
  3. 一時ファイルに書き出します (名前とサイズ、最大レコードなどを追跡します)。
  4. データの最後に到達するまで、手順 1 に戻ります。
  5. 最小限のマージを行うように、書き込まれたファイルのマージ ツリーを設定します。
  6. 最初の (唯一の?) マージ フェーズ入力ファイルのそれぞれから 1 行を読み取ります。
  7. 最小 (昇順ソートの場合) を次の一時ファイル (または最終ファイル) に書き込みます。
  8. 書き込まれたばかりのレコードを置き換える新しいレコードを取得します。
  9. 読み取るデータがなくなるまで、手順 7 に戻ります。
  10. 手順 6 に戻り、完了するまでマージを続けます。

buffSizeメモリのブロックが何を意味するのか詳しく説明していませんがa、メモリ内でソートできる配列があります。したがって、データを配列に読み込みます。クイックソートを使用して配列をソートします。次に、配列をディスクに書き出します。入力データがなくなるまで、読み取り、並べ替え、書き込みを繰り返します。次に、マージを行います...

于 2012-10-13T02:22:24.967 に答える