algorithm - ほとんどソートされたリストのソートアルゴリズム

Question

ファイルからの整数のリストに取り組んでいます。そして、並べ替えアルゴリズムを使用して、それらを降順に分類する必要があります。いくつかの並べ替えアルゴリズムの実行時間に精通しており、それらの使用が状況に応じて異なることも知っています。だから私の質問は:すでに 90% ソートされている任意のサイズのリストの最も速いソート アルゴリズムは何でしょうか? (私のファイルには 10.000 のエントリがありますが、そのうちの 9.500 は既にソートされています)。

ありがとうございました、

Answer 1

その std::sort C++ は内省的ソートを使用します。この場合、配列/リストは、最初に再帰の特定の深さのクイックソートを使用してソートされ、その後heapsortが続きます。約90％はわかりませんが、ヒープソートはすでにソートされた配列/リストでうまく機能しているようです...試してみることをお勧めします。