【Python】bisectモジュールで順序を維持したままソート済みリストに要素を挿入する方法

この記事では、ソート済みリストの順序を崩さずに新しい要素を挿入する方法を解説します。Pythonには標準ライブラリとして bisect モジュールが用意されており、これを使うとリスト内の適切な位置に要素を簡単に挿入できます。

bisectモジュールとは

bisect は二分探索（バイナリサーチ）を利用して、ソート済みシーケンスに対する挿入位置を高速に求めるための標準モジュールです。手動でループを回して挿入位置を探す必要がないため、コードがシンプルになり、パフォーマンスも向上します。

実装の手順

• bisect モジュールをインポートする
• 挿入対象のリストと、挿入したい要素を初期化する
• bisect.insort() メソッドを使って、適切な位置に要素を挿入する
• 結果のリストを出力して確認する

サンプルコード

# モジュールをインポート
import bisect

# リストと挿入する要素を初期化
numbers = [10, 23, 27, 32]
element = 25

# bisect.insort() で適切な位置に要素を挿入
bisect.insort(numbers, element)

# 結果を出力
print(numbers)

実行結果

[10, 23, 25, 27, 32]

実行すると、値 25 が 23 と 27 の間に自動的に挿入され、リスト全体が昇順に保たれていることがわかります。

補足：降順リストの場合

降順（大きい順）に並んだリストに挿入したい場合は、bisect.insort() の代わりに bisect.insort_right() や bisect.insort_left() を使い、key 引数や逆順処理と組み合わせることで対応できます。Python 3.10 以降では key 引数がサポートされているため、より柔軟な制御が可能です。

まとめ

リストを先頭から順に走査して挿入位置を見つける方法でも同じ結果は得られますが、要素数が多い場合には計算量が増え、非効率です。bisect.insort() を使えば二分探索によって O(log n) で挿入位置を特定できるため、ソート済みリストへの要素追加はこの方法を使うのがベストプラクティスといえます。