java - ソートされた配列で挿入ソートがクイックソートよりも速いのはなぜですか

Question

挿入ソートとクイックソートを比較しています。ほぼソートされた配列で qsort が遅い理由はわかりましたが、挿入ソートが非常に速い理由はわかりません。配列内のほぼ同じ数の要素を比較する必要がありますか?

Answer 1

ソートされた配列またはほぼソートされた配列で挿入ソートが高速である理由は、配列のソートされた部分に要素を挿入するときに、要素をほとんど移動する必要がないためです。たとえば、配列の並べ替えられた部分が1 2で、次の要素が3である場合、1回の比較を行うだけで、まったく2 < 3移動する必要がないことを確認でき3ます。結果として、すでにソートされた配列への挿入ソートは、要素ごとに1つの比較を行うだけでよいため、線形時間です。

Answer 2

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

Answer 3

クイックソートは、既にソートされた配列に対して最悪のケース (O(n^2) 時間の複雑さ) を持っています (ウィキペディアのクイックソートのエントリを参照してください)。

ピボット要素の選択に応じて、これはいくらか軽減できますが、同時に、挿入ソートの最良のケースは、まさに事前にソートされたケースです (そのような入力に対して O(n) 時間の複雑さがあります)。この特定のユースケースでは、クイックソートより優れています。

Answer 4

ソートされた入力は、挿入ソート (O(n)) の場合は最良のケースで、クイック ソートの場合は最悪のケース (O(n^2)) です。

それはすべて、両方のアルゴリズムの基本的な操作であるキー比較の数によって決定される複雑さと関係があります。

したがって、両方のアルゴリズムを見ると、挿入ソートでは、要素を挿入するときに左要素とのみ比較し、その完了と比較するのと同じように、 n 比較しかないことがわかります。一方、クイックソートの場合、ピボット要素をすべての左要素と比較し続ける必要があり、配列の種類は一定の1つの要素で減少し、約n ^ 2の比較になります。