バイナリ挿入ソート

1. 序章

このチュートリアルでは、バイナリ挿入ソートを紹介します。 これは挿入ソートの変形であり、バイナリ検索を使用してパフォーマンスを向上させます。

2. 挿入ソート

Insertion Sort は、の先頭で並べ替えられたサブ配列を繰り返し拡張することにより、入力配列を並べ替えます。

したがって、挿入ソートは最初にチェックし、その場合はスワップします。 次に、それが保持されるように挿入する場所を見つけます（はの-番目の要素であり、はの初期値です）。 これはこのように続き、ソートされたサブ配列を一度に1つの要素ずつ増やします。 を挿入する前に、並べ替えられたサブ配列は、最初はからの位置にある要素で構成されますが、現在は求められている順序になっています。

挿入ソートは、ソートも行う場所に直接挿入します。適切な位置に挿入すると、配列全体が非降順になります。

これは挿入ソートの擬似コードです：

2.1. 挿入ソートの複雑さ

最悪の場合の入力は、反対の方法でソートされた配列です（）。 その場合、挿入ソートはそれぞれの比較とスワップを行う必要があります。 合計で、スワップを実行し、同じ数の比較を実行します。 したがって、アルゴリズムには2次の最悪の場合の時間計算量があります。

挿入ソートの平均的なケースの複雑さもです。

3. バイナリ挿入ソート

バイナリ挿入ソートの背後にある考え方は、バイナリ検索を使用してそれぞれを配置する場所を見つけることです。 目標は、比較の数を減らすことです。

これはBISの擬似コードです。

3.1. バイナリ挿入ソートの複雑さ

スワップの数は、標準バージョンの挿入ソートと同じです。

最悪の場合、それぞれに対しておおよその比較を実行し、次に対して正確に1つの比較を実行します。

スターリングの近似を使用すると、次のようになります。

したがって、 Binary Insertion Sortが実行する比較の数は、では対数線形であると結論付けます。 ただし、スワップの数がであるため、最悪の場合、両方のアルゴリズムは漸近的に同じです。これは、平均的な場合の複雑さにも当てはまります。

4. バイナリ挿入ソートを使用する場合

結果として生じる複雑さが変わらないのに、なぜバイナリ検索を実装して挿入ソート内で使用する必要があるのでしょうか。 バイナリ挿入ソートは余分な作業の価値がないようです。 答えは、 漸近的に挿入ソートの標準バージョンと同等ですが、バイナリ挿入ソートは通常、実際にはより高速に動作します。 二分探索のため、比較する要素が少なくなります。

要素が複雑で、2つのオブジェクトの比較に時間がかかる場合、アイテムの比較に費やされる時間は、アイテムの交換に費やされる時間を支配します。このような場合、バイナリ検索によってもたらされる改善は大幅に報われます。 文字数などの単純なタイプを扱う場合、おそらく違いに気付かないでしょう。 ただし、ほとんどの実際のアプリケーションでは、データはより複雑になります。

5. 結論

この記事では、バイナリ挿入ソートについて説明しました。 これは挿入ソートの変形であり、バイナリ検索を使用して、を繰り返しながら入力のサブ配列のどこに配置するかを見つけます。

二分探索は比較の数を最悪の場合に減らしますが、 バイナリ挿入ソートは、挿入ソートと同じように2次の時間計算量を持っています。 それでも、実際には挿入ソートよりも通常は高速です。これは、2つの要素を交換するよりも比較にかなり時間がかかる場合に明らかです。