Python

【Python】リストにソート順で要素を追加する方法を解説

この記事では、Pythonでソートされたリストに要素を追加する際にソート順で要素を追加する方法を解説します。リストに要素を追加するたびにsort()メソッドで並び替えをすると効率が悪いので、bisectモジュールを使って二分探索アルゴリズムの力を借りましょう!

ソート順で要素を追加する

bisectモジュールのinsert系の関数を使うことでリストにソート順で要素を追加することができます。注意点として使用するリストはあらかじめソートしておく必要があります。

bisect.insort_left(a, x, lo=0, hi=len(a))
bisect.insort_right(a, x, lo=0, hi=len(a))
bisect.insort(a, x, lo=0, hi=len(a))

リストaにアイテムxをソート順で追加します。

すでにリストaにアイテムxと同等の値が存在する場合、insort_left()は同じ要素の左側にアイテムxを挿入し、insort_right()は同じ要素の右側にアイテムxを挿入します。

insort()insort_right()のエイリアスです。

import bisect

nums = [2, 4, 6, 1, 5]
# あらかじめソートしておく
nums.sort()
print(nums)

# 要素の追加
bisect.insort_left(nums, 3)
bisect.insort_right(nums, 3)
print(nums)

実行結果

[1, 2, 4, 5, 6]
[1, 2, 3, 3, 4, 5, 6]

どちら側に要素が挿入されたか分からないので自作クラスを使って検証してみる。

import bisect

# intとstrを持つクラス
class MyClass:
    
    def __init__(self, num, text=''):
        self.num = num
        self.text = text

    # < 演算子で比較できるようにする
    # 比較には num を使う
    def __lt__(self, other):
        if type(other) == MyClass: 
            return self.num < other.num
        raise TypeError()

    # 出力する際の書式
    def __repr__(self):
        return f'({self.num}, {self.text})'


l = [MyClass(1), MyClass(2), MyClass(3)] 

# 要素の追加
bisect.insort_left(l, MyClass(2, 'left'))
bisect.insort_right(l, MyClass(2, 'right'))

# 出力
print(l)

実行結果

[(1, ), (2, left), (2, ), (2, right), (3, )]

insort_left()は左側、insort_right()は右側に要素が追加されたのがわかります。

要素を挿入する範囲を指定するにはlo引数とhi引数を指定します。

import bisect

nums = [2, 4, 6, 1, 5]
nums.sort()
print(nums)

bisect.insort(nums, 3, 3, 4)
print(nums)

実行結果

[1, 2, 4, 5, 6]
[1, 2, 4, 3, 5, 6]

ソート順で要素を挿入できるインデックスの取得

ソート順で要素を挿入できる場所を探して、そのインデックスを取得することもできます。こちらの関数を使用する際にもリストはあらかじめソートしておく必要があります。

bisect.bisect_left(a, x, lo=0, hi=len(a))
bisect.bisect_right(a, x, lo=0, hi=len(a))
bisect.bisect(a, x, lo=0, hi=len(a))

戻り値がインデックスなだけで使い方はinsortと変わりません。

import bisect

nums = [2, 4, 6, 1, 5, 3]
nums.sort()
print(nums)

print(bisect.bisect_left(nums, 3))
print(bisect.bisect_right(nums, 3))

実行結果

[1, 2, 3, 4, 5, 6]
2
3

Linkbisect --- 配列二分法アルゴリズム — Python ドキュメント

最短3か月でエンジニア転職『DMM WEBCAMP COMMIT』