ソートされた配列がソートされた配列のクイックソートより速くなる理由

Question

クイックソートと挿入ソートを比較しています。私はqソートがほぼソートされた配列の方が遅い理由を理解しましたが、なぜインパージョンソートがすごく早いのか理解できません。

Answer 1

いくつかの要因によって異なります。挿入ソートは、小さなデータセットのクイックソートより効率的です。また、バッキングリストの実装（LinkedListまたはArrayList）にも依存します。最後に、入力データに何らかの並べ替えがあるかどうかによっても異なります。たとえば、入力データが既に逆の順序でソートされていて、LinkedListを使用している場合、挿入ソートは高速になります。

Answer 2

クイックソートは、すでにソートされた配列の最悪の場合（O（n^2）時間の複雑さ）です（quicksort entry on Wikipedia参照）。

ピボット要素の選択に応じて、多少緩和することができますが、同時に、挿入ソートの最適なケースは、あらかじめソートされたケースです（このような入力にはO（n） ）、この特定のユースケースではクイックソートを打ち負かすつもりです。

Answer 3

ソートされた配列やほぼソートされた配列の方が挿入のソートが速い理由は、配列のソートされた部分に要素を挿入するときに、要素をまったく動かす必要がないからです。たとえば、配列のソートされた部分が1 2で、次の要素が3の場合、3を移動する必要がないと判断するためには、1つの比較（2 < 3）を実行するだけです。その結果、既にソートされた配列の挿入ソートは、要素ごとに1つの比較しか行う必要がないため、線形時間です。

Answer 4

ソートされた入力は、挿入ソート（O（n））およびクイックソート（O（n^2））のワーストケースに最適です。

両方ともアルゴリズムの基本操作であるキー比較の回数で決まる複雑さと関連しています。

したがって、両方のアルゴリズムを見ると、挿入ソートでは、要素を挿入したときと比較してn個の比較しかないことが分かります。一方、クイックソートの場合は、ピボット要素を左要素と比較し、配列の種類を一定の係数で比較して、約n^2の比較を続けなければなりません。