.txtファイルのMergesort行

Question

私は複数のソートされた行を持つファイルを持っています。 今、私はこのファイルをすべて新しいファイルの一つのマージされた行に並べ替えたいと思っています。一度にすべての数値をロードせずに。

これは私のファイルの一部です：

12,86,280,304,350,359,371,391,405,548, 
 
255,264,325,346,435,466,483, 
 
39,114,214,298,317,377,428,438,575, 
 
35,165,183,281,336,367,386,418,438,593, 
 
44,77,97,117,122,156,251,415,533, 
 
109,155,163,172,212,226,340,358,452,577,592, 
 
33,74,91,204,256,307,357,388,534,552,554,570, 
 
50,99,246,309,345,358,395,405,419,425,566,

今、私は、ソート、それらをマージしたいので、最初は、私は、ファイルが持っているどのくらいのラインを知る必要があります。それから私はすべての最初の要素を取得し、それらを比較する必要があります。私は新しいファイルに書き込みます。それから私はちょうど私が書いた線から2番目の数字を得なければならない。そして、それらを他の行の最初の数と比較してください。どうすればいいの？私はのArrayListのためのマージソートを書いた：

 //as long as there is unsorted data 
 
     while (listOfOutputs.size() > 0) { 
 
      //Set the lowest undefined 
 
      List<Integer> lowest = null; 
 
      for (List<Integer> list : listOfOutputs) { 
 
       //if the lowest is undefined, I'm the lowest 
 
       if (lowest == null) { 
 
        lowest = list; 
 
        //Else am I lower then the lowest? Then I'm the lowest 
 
       } else if (list.get(0) < lowest.get(0)) { 
 
        lowest = list; 
 
       } 
 
      } 
 

 
      //Finally the lowest is added to the sorted list and removed to from his own list. 
 
      assert lowest != null; 
 
      sortedList.add(lowest.remove(0)); 
 

 
      //Is the size of the list which contained to lowest now 0, remove him from the listOfOutputs 
 
      if (lowest.size() == 0) listOfOutputs.remove(lowest); 
 
     }

しかし、私は、私のファイルをソート1にこれをリライトする方法がわかりません。これをリストにロードすることなく、どのようにすればいいですか？

スヴェン

Answer 1

あなたは、単一のソート行が生成されるまでのプロセスを繰り返し、単一の行に一度に2行をマージするシンプルな2ウェイ・マージを使用することができます。 kはラインの数であると仮定すると、

または

は、おそらく最小の最初の要素を持っているラインを見つける最適化するために、ヒープを使用して、k個の方向マージを実装することができます。各ヒープ要素には、その行の現在の要素に対する索引（またはポインター）の行とその等価物への参照が含まれています。ヒープの先頭が現在の最小要素を持つ行を参照するように、ヒープは各行の現在の要素によって順序付けられます。ヒープは、すべてのk行の最初の要素によって初期化されます。

各マージステップで、ヒープの先頭からの行（最小の要素を持つ行）が削除され、その最小の要素が出力行に追加され、最小の要素を持つ行がヒープは次の要素に基づいています。

行の終わりに達すると、マージはk-1ウェイマージに縮小され、最終的にマージされた出力にコピーされる1行だけに終わります。