Pythonで実装するバイナリ挿入ソート：二分探索と挿入ソートを組み合わせた効率的な並べ替え

はじめに

この記事では、「バイナリ挿入ソート（Binary Insertion Sort）」を使って配列を並べ替えるPythonプログラムについて解説します。名前の通り、このアルゴリズムは二分探索（バイナリサーチ）と挿入ソートの2つの考え方を組み合わせたものです。

問題の概要

問題文： 整数の配列が与えられます。バイナリ挿入ソートの手法を用いて、この配列を昇順に並べ替えてください。

通常の挿入ソートでは、挿入すべき位置を先頭から順番に線形探索で探します。一方、バイナリ挿入ソートでは「すでにソート済みの部分列」に対して二分探索を適用することで、挿入位置を効率的に特定できます。

実装例

それでは、実際のコードを見てみましょう。

# ソート処理
def insertion_sort(arr):
    for i in range(1, len(arr)):
        temp = arr[i]
        # 二分探索で挿入位置を求める
        pos = binary_search(arr, temp, 0, i) + 1
        # 要素を後ろへずらす
        for k in range(i, pos, -1):
            arr[k] = arr[k - 1]
        arr[pos] = temp

def binary_search(arr, key, start, end):
    # 挿入位置を再帰的に探索
    if end - start <= 1:
        if key < arr[start]:
            return start - 1
        else:
            return start
    mid = (start + end)//2
    if arr[mid] < key:
        return binary_search(arr, key, mid, end)
    elif arr[mid] > key:
        return binary_search(arr, key, start, mid)
    else:
        return mid

# メイン処理
arr = [1,5,3,4,8,6,3,4]
n = len(arr)
insertion_sort(arr)
print("Sorted array is:")
for i in range(n):
    print(arr[i],end=" ")

出力結果

Sorted array is :
1 3 3 4 4 5 6 8

コードの解説

このプログラムの流れは以下の通りです。

1. insertion_sort関数： 配列の2番目の要素（インデックス1）から順に走査し、現在注目している要素を一時変数 temp に保存します。その後、binary_search を呼び出して、ソート済み部分の中での正しい挿入位置 pos を取得します。位置が確定したら、それより後ろの要素を1つずつ右へずらし、temp を適切な場所に挿入します。

2. binary_search関数： 探索範囲が十分に小さくなるまで再帰的に範囲を半分に絞り込んでいきます。中央の値とキーを比較することで、挿入すべき位置を高速に特定します。すべての変数はローカルスコープ内で宣言されており、それぞれの参照関係は処理の流れの中で明確になっています。

計算量について

バイナリ挿入ソートの最大の特徴は、比較回数の削減にあります。

• 比較回数： 二分探索により、各要素の挿入位置の判定は O(log n) 回の比較で済みます。全体では約 O(n log n) 回の比較となります。
• 要素の移動： 一方、要素をずらす操作は最悪の場合 O(n²) となるため、全体の計算量は O(n²) のままです。

そのため、比較コストが高いデータや、ほぼ整列済みのデータを扱う場合に、通常の挿入ソートよりも有利になります。

まとめ

この記事では、Pythonを使ってバイナリ挿入ソートを実装する方法を学びました。二分探索を組み合わせることで挿入位置の特定が高速化され、比較回数を大幅に減らせる点が大きなメリットです。ソートアルゴリズムの理解を深めるための良い題材なので、ぜひ自分でもコードを動かして挙動を確認してみてください。