C++で実装するバイナリ挿入ソート（二分挿入ソート）の解説とサンプルコード

バイナリ挿入ソートとは

バイナリ挿入ソート（Binary Insertion Sort）は、挿入ソートの一種で、要素を挿入すべき正しい位置を探す際に二分探索（バイナリサーチ）を利用するソートアルゴリズムです。

通常の挿入ソートは、配列内でその要素が属するべき位置を見つけ、そこへ要素を挿入していくことで整列を行う手法です。一方、二分探索は、配列の中央の値と比較しながら範囲を絞り込んでいくことで、目的の位置や要素を効率的に見つける探索手法です。

二分探索の計算量は対数時間 O(log n) であるため、挿入位置の探索にかかる時間も線形探索から対数オーダーへと大幅に削減されます。ただし、要素のシフト処理自体は O(n) かかるため、全体の計算量は O(n²) のままですが、比較回数は通常の挿入ソートより少なくて済むという利点があります。

アルゴリズムの流れ

1. 配列の2番目の要素から順に「未整列部分」の要素を選択します。
2. 選択した要素について、既に整列済みの左側の部分配列に対して二分探索を行い、挿入位置を求めます。
3. 挿入位置以降の要素を1つずつ後ろへずらします。
4. 選択した要素を挿入位置に配置します。
5. これを配列の末尾まで繰り返します。

C++による実装例

以下のプログラムは基本的な挿入ソートの構造を保ちつつ、挿入位置の決定に標準的な線形探索の代わりに二分探索を使用したものです。

#include <iostream>
using namespace std;

// 二分探索により挿入位置を求める関数
int binarySearch(int arr[], int item, int low, int high) {
    if (high <= low)
        return (item > arr[low]) ? (low + 1) : low;
    int mid = (low + high) / 2;
    if (item == arr[mid])
        return mid + 1;
    if (item > arr[mid])
        return binarySearch(arr, item, mid + 1, high);
    return binarySearch(arr, item, low, mid - 1);
}

// バイナリ挿入ソート本体
void BinaryInsertionSort(int arr[], int n) {
    int i, loc, j, selected;
    for (i = 1; i < n; ++i) {
        j = i - 1;
        selected = arr[i];
        // 整列済み部分 [0, j] から挿入位置を二分探索で取得
        loc = binarySearch(arr, selected, 0, j);
        // 要素を後ろへずらす
        while (j >= loc) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = selected;
    }
}

int main() {
    int arr[] = {12, 56, 1, 67, 45, 8, 82, 16, 63, 23};
    int n = sizeof(arr) / sizeof(arr[0]), i;
    BinaryInsertionSort(arr, n);
    cout << "Sorted array is : \n";
    for (i = 0; i < n; i++)
        cout << arr[i] << "\t";
    return 0;
}

実行結果

Sorted array is :
1 8 12 16 23 45 56 63 67 82

計算量のまとめ

• 最悪計算量： O(n²)（要素のシフトが支配的）
• 比較回数： O(n log n)（二分探索により削減）
• 空間計算量： O(1)（in-place ソート）
• 安定性： 安定ソート（等しい要素の相対順序は保持される）

このように、バイナリ挿入ソートは特に「比較コストが高いデータ」や「ほぼ整列済みのデータ」に対して有効な手法です。C++では std::upper_bound を使えば、二分探索部分を標準ライブラリで簡潔に置き換えることも可能です。