algorithm - シリアルデータをバッファで並べ替える

Question

データ長より小さいバッファを使用してシリアル入力からデータをソートするアルゴリズムはありますか?

たとえば、一度だけ読み取ることができる 100 バイトのシリアル データと 40 バイトのバッファがあります。そして、ソートされたバイトを出力する必要があります。

Javascriptで必要ですが、一般的なアイデアは大歓迎です。

Answer 1

この種の並べ替えは、1 回のパスでは実行できません。

例を使用すると、40 バイトのバッファーがいっぱいになったので、次のバイトのためのスペースを確保するためにバイトの出力を開始する必要があるとします。ソートされたデータを印刷するには、最初に最小バイトを印刷する必要があります。ただし、最小バイトが読み取られていない場合は、まだ印刷できない可能性があります。

あなたの質問に最も近いのは、メモリに収まらないデータを並べ替えるために複数のパスを必要とする外部並べ替えアルゴリズムである可能性があります。つまり、処理パスの出力を保存できる周辺機器がある場合、メモリより大きいデータを O(log(N/M)) パスで並べ替えることができます。ここで、N は問題のサイズで、M は問題のサイズです。あなたのメモリのサイズ。

外部ソート用の従来のストレージ周辺機器はテープ ドライブです。ただし、ディスク ドライブ (種類を問わず) に対しても同じアルゴリズムが機能します。また、キャッシュ階層が深くなるにつれて、外部ソートの原則はメモリ内ソートにもより関連するようになります。キャッシュを無視するアルゴリズムを調べてみてください。