★★ Java の宿題ここで答えます Part 68 ★★

★★ Java の宿題ここで答えます Part 68 ★★ at TECH

182:デフォルトの名無しさん
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」
となって全体のソートが完了する。

こんな感じ。

次ページ

続きを表示

1を表示