c++ - O(N log N) 読み取りと O(N) 書き込みによる int の外部ソート

Question

読み取りと書き込みintを伴う s の外部ソートの要件を満たすために使用するアルゴリズムに興味がありますO(N log N)O(N)

Answer 1

そのタイプのソート (データがすべて一度にコアに収まらない場合) のアルゴリズムを求めている場合、私の解決策は、トップエンドのマシンがほとんどのマシンよりもメモリが少なかった「革命」のごく初期の時代から来ています。現代の電卓。

私はbig-Oプロパティを解決していませんが、O（n）読み取り、O（n log n）ソートフェーズ（選択したソート方法によって異なります）、およびO（n）書き込みになると思います。

データ セットに 100 万の要素があり、一度に 100,000 しかメモリに収まらないとします。これが私がすることです：

• 最初の 100,000 を読み取り、それらを並べ替えて、その並べ替えられたリストを書き戻します。
• 100,000 のグループごとにこれを行います。
• 10 個のグループに対してマージ操作を実行します。

つまり、グループ内で 10 個のグループを並べ替えたら、各グループから最初のエントリを取得します。

次に、それらの 10 のうち最も低いもの (100 万全体の中で最も低いもの) を出力ファイルに書き込み、そのグループから次のものをその場所で読み取ります。

次に、10 個のうち最も低いものを選択し、書き出して、同じグループから置き換えます。このようにして、最終的な出力は、100 万のエントリのソート済みリスト全体になります。

Answer 2

外部マージソートアルゴリズムをチェックしてください。

Answer 3

このページを試してみてください: Sorting Algorithms . いくつかのアルゴリズムの素敵なアニメーションを表示するだけでなく、それらがどのように機能し、複雑であるかを説明しています。