Python의 bisect 모듈은 새로운 요소를 삽입할 때마다 리스트 전체를 다시 정렬할 필요 없이, 리스트가 항상 정렬된 상태를 유지하도록 도와주는 표준 라이브러리입니다. 내부적으로 이진 탐색(binary search) 알고리즘을 기반으로 동작하며, 대표적인 함수로 insort_left와 insort_right가 있습니다.
insort_left 함수
bisect.insort_left()는 지정한 값을 리스트의 적절한 위치에 삽입한 후 정렬된 리스트를 반환합니다. 만약 동일한 값이 이미 리스트에 존재한다면, 새 값은 해당 값들 중 가장 왼쪽(앞쪽) 위치에 삽입됩니다.
이 함수는 최대 4개의 인자를 받습니다.
- a: 삽입 작업을 수행할 대상 리스트
- x: 삽입할 값
- lo: 탐색을 시작할 위치 (기본값 0)
- hi: 탐색을 종료할 위치 (기본값 리스트의 길이)
insort_right 함수
bisect.insort_right()는 insort_left와 유사하게 동작하지만, 동일한 값이 이미 존재하는 경우 새 값을 기존 항목들의 오른쪽(뒤쪽)에 삽입한다는 점이 다릅니다. 즉, 같은 값이 여러 개 있을 때 삽입되는 위치가 오른쪽 끝이라는 차이만 있을 뿐입니다.
문법(Syntax)
bisect.insort_left(a, x, lo=0, hi=len(a)) bisect.insort_right(a, x, lo=0, hi=len(a)) # a : 삽입 대상 시퀀스(리스트) # x : 삽입할 값 # lo, hi : 탐색 범위의 시작 인덱스와 끝 인덱스
예제
아래 예제에서는 두 개의 리스트에 각각 bisect.insort_left와 bisect.insort_right를 적용하여 그 차이를 확인해 봅니다.
import bisect
listA = [11, 13, 23, 7, 13, 15]
print("Given list:", listA)
bisect.insort_left(listA, 14)
print("Bisect left:\n", listA)
listB = [11, 13, 23, 7, 13, 15]
print("Given list:", listB)
bisect.insort_right(listB, 14, 0, 4)
print("Bisect right:\n", listB)
실행 결과
위 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.
Given list: [11, 13, 23, 7, 13, 15]
Bisect left:
[11, 13, 23, 7, 13, 14, 15]
Given list: [11, 13, 23, 7, 13, 15]
Bisect right:
[11, 13, 14, 23, 7, 13, 15]
주의 사항
bisect 모듈의 삽입 함수들은 리스트가 이미 정렬되어 있다고 가정하고 이진 탐색을 수행합니다. 따라서 위 예제처럼 정렬되지 않은 리스트에 사용하면 결과가 예상과 다르게 나올 수 있습니다. 실무에서는 sorted() 함수 등으로 리스트를 먼저 정렬한 뒤 사용하는 것이 안전합니다.