c - 元のファイルの内容を格納するために配列を使用せずに、ファイル内の 100 万個の整数を並べ替えて別のファイルに保存する方法は?

Question

100 万のランダムな入力を含むファイルを作成し、それらを並べ替えてから、並べ替えられたリストを新しいファイルに書き込むプログラムを作成しています。

入力ファイル全体を配列にコピーすることなく要素をソートできる効率的な方法はありますか - >ソート - >出力ファイルに書き戻す？

Answer 1

「簡単な」解決策は、「出力ファイルにまだ格納されていない最小の [1] 番号」を見つけるリストを反復処理し、低い番号が見つからなくなるまで繰り返すことです。ただし、おそらくソートされていないファイル全体の 1M の読み取りを意味するため、これは非常に遅くなります。しかし、それは多くのメモリを消費しません...

残念ながら、他の方法では、ファイル (または一部) をメモリに読み込む必要があります。メモリに読み込むのに十分なメモリがある場合、ディスク上での並べ替えはかなりくだらない方法です。16GB のマシンで 40GB の数字のリストを並べ替えるとしたら、もちろん選択の余地はありません。ただし、十分なメモリがある場合は、すべてをメモリに読み込んで再度書き戻すことが常に最良の選択です。

[1] または、「高から低」に並べ替える場合は最高。

Answer 2

二分探索木を使用して出力ファイルに書き戻すには、次のアルゴリズムを使用できます。

void output_to_file(FILE* file , struct* binTree)
{
     if(binTree != NULL)
     {
         output_to_file(binTree->left);
         fprintf(file , "%d/n" , binTree->num); //num is the member of the structure that carrys the number
     output_to_file(binTree->right);
     }
}