algorithm - ヒープソートまたはクイックソートの方が良いですか?

Question

私は会社の書面によるラウンドを行いました。疑問があるのですが、誰か助けてもらえますか?

次のうち、最も高速なソート アルゴリズムはどれですか?
a - バブル ソート
b - シェル ソート
c - ヒープ ソート
d - クイック ソート

私は、クイックソートとヒープソートの両方がO（nlogn）の時間の複雑さを持っていることに混乱しています。

Answer 1

「最速」のソートアルゴリズムはありません。

アルゴリズムの理論上のパフォーマンスは、常に入力データに依存します。それぞれの最悪のケースでは、ヒープ ソートはクイック ソートより高速です。平均的なケースでは、クイック ソートの方が高速です。他のすべてのアルゴリズムよりも優れたパフォーマンスを発揮するように、アルゴリズムごとに最適なケースをカスタマイズすることはおそらく可能です。

これが、実際にIntrosortのような「ハイブリッド」アルゴリズムが存在する理由です。Introsort は Quick sort から始まり、Quick sort がこの特定の入力に苦労していることがわかると Heap sort に切り替わります。

その上、アルゴリズムの実際のパフォーマンスは、特定のハードウェア プラットフォームでどれだけうまく機能するかによって大きく影響を受ける可能性があります。理論的に「速い」アルゴリズムは、原始的で「遅い」アルゴリズムがハードウェアの特性とよりよく「同期」している場合、惨めに負ける可能性があります。

Answer 2

ウィキペディアを参照してください: ヒープソート

ヒープソート: 実際には、ほとんどのマシンで適切に実装されたクイックソートよりも多少遅くなりますが、最悪の場合の O(n log n) ランタイムが有利であるという利点があります。

Answer 3

平均的な場合：クイックソート。O（nlgn）の実行時間の定数の方が優れているためです。

最悪の場合：ヒープソート。最悪の場合、クイックソートの実行時間はO（n ²）です。