Pythonでソート済みリストの順序を保ったまま要素を挿入する2つの方法

本記事では、ソート済みのリストに対して、その並び順を崩すことなく新しい要素を挿入する方法について解説します。

問題文

リストが与えられたとき、既存のソート順を維持したまま、指定した要素を適切な位置に挿入する必要があります。

この問題を解くには、主に以下の2つのアプローチがあります。

アプローチ1：線形探索による力まかせ法（ブルートフォース）

まず、挿入すべき位置をリストの先頭から順に走査して見つけ出し、そこへ要素を挿入するというシンプルな方法です。挿入する要素より大きい値が最初に現れた位置に、新しい要素を差し込みます。

コード例

def insert(list_, n):
    # 挿入位置を探索
    for i in range(len(list_)):
        if list_[i] > n:
            index = i
            break
    # 要素の挿入
    list_ = list_[:i] + [n] + list_[i:]
    return list_

# 動作確認
list_ = ['t','u','t','o','r']
n = 'e'
print(insert(list_, n))

出力

['e', 't', 'u', 't', 'o', 'r']

文字「e」が先頭に挿入され、アルファベット順が保たれていることがわかります。

アプローチ2：bisectモジュールを使う方法

Pythonの標準ライブラリには、二分探索を利用してソート済みリストへの挿入を簡単に行える bisect モジュールが用意されています。bisect.insort() を使えば、挿入位置の計算と実際の挿入を一度に行うことができます。

コード例

# 標準ライブラリのbisectモジュールを使用
import bisect

def insert(list_, n):
    bisect.insort(list_, n)
    return list_

list_ = ['t','u','t','o','r']
n = 'e'
print(insert(list_, n))

出力

['e', 't', 'u', 't', 'o', 'r']

両者の違いとパフォーマンス

アプローチ1の線形探索では挿入位置の特定にO(n)の計算量が必要ですが、bisectモジュールを使った二分探索ではO(log n)で挿入位置を見つけられます。そのため、要素数が多いリストを扱う場合には、bisectモジュールの利用が推奨されます。

まとめ

本記事では、ソート済みリストの並び順を維持しながら要素を挿入する2つの方法――自前で挿入位置を探索する方法と、標準ライブラリのbisectモジュールを活用する方法――について学びました。小規模なデータなら前者でも十分ですが、パフォーマンスを重視する場面では後者を選ぶとよいでしょう。