알고리즘 - 이진 삽입 정렬

단순 삽입 정렬은 배열 원소 수가 많이지면 비교, 교환 비용이 커지는데

이진 삽입 정렬을 사용하면 정렬을 마친 배열을 제외하고

원소를 삽입해야 할 위치를 검사해서 비용을 줄일 수 있습니다.

 

---

def binary_insertion_sort(a):
    n = len(a)
    for i in range(1, n):
        key = a[i]
        pl = 0
        pr = i - 1

        while True:
            pc = (pl + pr) // 2
            if a[pc] == key:
                break
            elif a[pc] < key:
                pl = pc + 1
            else:
                pr = pc - 1
            if pl > pr:
                break

        if pl <= pr:
            pd = pc + 1
        else:
            pd = pr + 1
        print(f'pl: {pl}, pr: {pr}, pd: {pd}')
        for j in range(i, pd, -1):
            a[j] = a[j-1]

        a[pd] = key


print('이진 삽입 정렬')
num = int(input('원소 수 입력: '))
x = [None] * num    # 원소 수가 num인 배열을 생성

for i in range(num):
    x[i] = int(input(f'x[{i}]: '))

print(''.join(str(x)))
binary_insertion_sort(x)
print(''.join(str(x)))

 

이진 검색에서 사용했던 방법과 비슷합니다.

6

4

3

7

1

9

8

위 배열에서 정렬을 시작하는 원소는 4입니다.

그럼 검색 범위는 pl = 0, pr = 0 이렇게 시작합니다.

검색 범위의 가운데 인덱스 pc는 0이 되고, a[0]인 6보다 4가 작기 때문에 pr = pc - 1이 되고

pr이 pl보다 작으므로 while문이 종료됩니다.

그럼 현재 pl = 0, pr = -1이고 pd는 pr + 1로 0입니다.

pd 값은 검색 범위 가장 끝 인덱스라 생각하시면 됩니다.

for문에서 a[1]을 6으로 바꿔주고, a[pd] = key >> a[0] = 4 이렇게 교환이 됩니다.

 

이렇게 검색 범위를 축소하고 가운데 값을 기준으로 검색 범위를 좁혀 나가는 것이

이진 삽입 정렬입니다.

 

---

파이썬 표준 라이브러리에서 bisect모듈의 insort()함수를 사용하면

이진 삽입 정렬을 간단하게 구현 가능합니다.

 

import bisect
def binary_insertion_sort(a):
    for i in range(1, len(a)):
        bisect.insort(a, a.pop(i), 0, i)
        # insort(a, x, lo, hi)

print('이진 삽입 정렬')
num = int(input('원소 수 입력: '))
x = [None] * num    # 원소 수가 num인 배열을 생성

for i in range(num):
    x[i] = int(input(f'x[{i}]: '))

print(''.join(str(x)))
binary_insertion_sort(x)
print(''.join(str(x)))

 

insort함수는 정렬된 상태를 유지하면서 a[lo] ~ a[hi] 사이에 x를 삽입합니다.