09/09/04 06:15:27
>>177
もう見てないかも知れんが。
3 5 4 1 9 8 7 2 15 を例にとると、
・データの範囲を０～１９とする。
・データは3つまでしか読めない。
という仮定で、簡略化のため、テンポラリファイルにも3つの値しか書きこまないとする。
テンポラリファイルは7つできる。それぞれ0.dat～6.datとする。
最初に、3つ読み込む
メモリには「３，４，５」がある。
これを0.dat～6.datに振り分ける。
この場合、1.datに３，４，５が書き込まれ、他のテンポラリファイルには何のデータもない。
次にもう3つ読む。
メモリには「１，９，８」がある。
これを振り分けると、1→0.dat、9→3.dat、8→2.datとなる。
最後に3つ読み振り分ける。7→2.dat、2→0.dat、15→5.datとなる。
この時点で振り分け終わり。各テンポラリファイルには、
0.dat:「2」、1.dat:「3,4,5」、2.dat:「8,7」、3.dat:「9」、4.dat:「」、5.dat:「」、6.dat:「15」
というデータが入っている。
次に各テンポラリファイルごとに読み込みなおして、クイックソート→書き戻しを行う。
これでテンポラリファイルの内容は
0.dat:「2」、1.dat:「3,4,5」、2.dat:「7,8」、3.dat:「9」、4.dat:「」、5.dat:「」、6.dat:「15」
となる。これを連結すれば
「2,3,4,5,7,8,9,15」
となって全体のソートが完了する。
こんな感じ。