c++ - 一部の数値がすでに並べ替えられている配列を部分的に並べ替える

Question

配列を降順で部分的に並べ替える必要があります。この場合、一部の数値はすでに並べ替えられています。

それを効率的に実行できる関数か、効率的なアルゴリズムか。

Answer 1

Timsortは、その場合のために特別に設計されています。

Timsort は、マージ ソートと挿入ソートから派生したハイブリッド ソート アルゴリズムであり、多くの種類の実世界のデータに対して適切に機能するように設計されています。Python プログラミング言語で使用するために、2002 年に Tim Peters によって発明されました。このアルゴリズムは、既に順序付けされているデータのサブセットを見つけ、そのサブセットを使用してデータをより効率的に並べ替えます。

もう 1 つの代替方法はSmoothsortで、これも部分的に並べ替えられたデータを利用するように設計されています。

これは、1981 年に Edsger Dijkstra によって開発されたヒープソートのバリエーションです。ヒープソートと同様に、スムーズソートの上限は O( n log n ) です。スムーズソートの利点は、入力がすでにある程度ソートされている場合、 O( n ) 時間に近づくことですが、ヒープソートは、最初のソート状態に関係なく平均 O( n log n ) です。

Answer 2

std::sort一般に。

正確な実装の詳細は実装の品質ですが、の優れた実装でstd::sortは、データの部分的に並べ替えられた性質を利用する必要があります。libc++たとえば、します。

ソートされたピースがどこにあるかがわかっている場合は、を使用できることに注意してくださいstd::inplace_merge。たとえば、[1、7 v）vectorが並べ替えられ、[7、10）も並べ替えられているとすると、使用できますがstd::inplace_merge(v.begin() + 1, v.begin() + 7, v.begin() + 10)、エラーが発生しやすくなります。

結果の順序について：自分<に合わない場合は、自由に独自の比較機能を提供してください。

Answer 3

ループ内でソートしている場合は、代わりに Treap または赤黒ツリーを検討してください。Treap は平均して高速であり (ただし、標準偏差が大きい)、赤黒木は操作時間のばらつきが小さくなります (平均操作時間はそれほど良くありませんが、操作時間の標準偏差は低くなります)。IOW、バッチ アプリケーションの場合は Treap を使用します。対話型アプリケーションの場合は、赤黒のツリーが必要になる場合があります。

ループでソートしていない場合は、Timsort.