algorithm - 二分探索による挿入ソート

Question

挿入ソートを実装する場合、バイナリ検索を使用して、要素 i を挿入する配列の最初の i - 1 要素内の位置を特定できます。

これは、必要な比較の数にどのように影響しますか? このようなバイナリ検索を使用すると、挿入ソートの漸近的な実行時間にどのような影響がありますか?

これにより比較の数が減ると確信していますが、その理由は正確にはわかりません。

Answer 1

ウィキペディアから直接：

比較のコストがスワップのコストを超える場合、たとえば、参照によって格納された文字列キーや人間の操作 (並べて表示されたペアのいずれかを選択するなど) の場合のように、バイナリ挿入ソートを使用すると、よりよい性能。二分挿入ソートは、二分探索を使用して新しい要素を挿入する正しい位置を決定するため、最悪の場合、 O(n log n) である⌈log2(n)⌉ 比較を実行します。挿入ごとに一連のスワップが必要なため、アルゴリズム全体の実行時間は平均で O(n2) です。

ソース：

http://en.wikipedia.org/wiki/Insertion_sort#Variants

次に例を示します。

http://jeffreystedfast.blogspot.com/2007/02/binary-insertion-sort.html

これにより比較の数が減ると確信していますが、その理由は正確にはわかりません。

挿入ソートとバイナリ検索を既に知っている場合は、かなり簡単です。挿入ソートでピースを挿入するときは、以前のすべてのピースと比較する必要があります。この [2] を正しい場所に移動したいとします。正しい場所を見つける前に、7 つのピースと比較する必要があります。

[1][3][3][3][4][4][5] -> [2] <- [11][0][50][47]

ただし、中間点から比較を開始すると (二分探索のように)、比較できるのは 4 個だけです。これを行うことができるのは、左のピースがすでに順番に並んでいることがわかっているからです (ピースが順番に並んでいる場合にのみ、バイナリ検索を実行できます!)。

数千個 (または数百万個) の部品がある場合、これにより多くの時間を節約できると想像してください。これが役立つことを願っています。|=^)

Answer 2

効率的なバイナリ検索のための優れたデータ構造がある場合、O(log n) の挿入時間はほとんどありません。逆に、任意の位置への高速挿入に適したデータ構造は、二分探索をサポートする可能性は低いです。

挿入ソートを使用した最適な比較検索の O(n log n) パフォーマンスを達成するには、O(log n) 二分探索と O(log n) 任意挿入の両方が必要です。

Answer 3

配列が (バイナリ検索を実行するために) ソートされていると仮定すると、内部ループは 1 回の比較の直後に終了するため (前の要素が小さいため)、比較は減りません。一般に、挿入ソートの比較回数は、最大で反転回数に配列サイズを加えた値 - 1 です。

ソートされた配列の反転数は 0 であるため、既にソートされた配列の比較の最大数は N - 1 です。