[解決済み] クイックソートとヒープソートの比較

質問

クイックソートとヒープソートはどちらもインプレースソートを行います。どちらがよいのでしょうか？また、どのような場合にどちらを使うべきでしょうか？

解決方法は？

本紙 は、いくつかの分析を行っています。

また、Wikipediaより。

の最も直接的なライバルは クイックソートはヒープソートです。ヒープソートは よりも多少遅くなります。 しかし、最悪の場合の実行は は常にΘ(nlogn)である。クイックソートの方が 通常、より高速ですが 最悪性能の可能性 ただし、イントロソートの変種では ヒープソートに切り替わります。 が検出されます。もし、事前に ヒープソートが発生することを 直接使用する方が イントロソートを待つより速い に切り替えることができます。