Jon Bentley によるProgramming Pearlsを読んでいます(参照)。
ここで著者は、マージソート、マルチパスソートなどのさまざまなソートアルゴリズムについて言及しています。
質問:
入力ファイルを 1 回読み取り、作業ファイルを使用して出力ファイルを 1 回だけ書き込むことにより、マージソートのアルゴリズムはどのように機能しますか?
作成者は、40 パス、つまりマルチパス ソート アルゴリズムが、出力ファイルに 1 回だけ書き込み、作業ファイルなしで動作することをどのように示していますか?
誰かが上記を簡単な例で説明できますか?たとえば、3桁を格納するメモリと10桁を格納するなどです。9,0,8,6,5,4,1,2,3,7
これは、優れた本であるJon Bentley の Programming Pearls, 2nd Edn (1999) の第 1 章からのものです。初版の同等の例は少し異なります。マルチパス アルゴリズムでは、データに対して 27 回のパスしか行われませんでした (そして、使用可能なメモリが少なくなりました)。
Jon Bentley によって説明された並べ替えには、特別なセットアップの制約があります。
入力ファイルの 1 回の読み取りでは、入力からメモリに収まる数の行を丸呑みし、そのデータを並べ替えて、作業ファイルに書き込みます。入力ファイルにデータがなくなるまで、すすいで繰り返します。
次に、作業ファイルを読み取り、並べ替えられた内容を単一の出力ファイルにマージして、プロセスを完了します。極端な場合、プログラムはすべての作業ファイルを一度に読み取ることができないため、新しい大きな作業ファイルを作成する必要がある場合があります。その場合は、処理できる最大数の入力を最終パスに配置し、中間パスで適切な数のファイルをマージします。
これは汎用アルゴリズムです。
ここで、データの固有のプロパティが活用されます。数値は一意で範囲が限られているため、アルゴリズムは最初にファイルを読み取り、範囲の最初の 40 分の 1 から数値を抽出し、それらを並べ替えて書き込みます。次に、範囲の 2 番目の 40 分の 1、次に 3 番目、...、そして最後の 40 分の 1 を抽出します。
これは、数値の性質を利用した特殊な目的のアルゴリズムです。