앞에 적은 삽입정렬을 보면 알겠지만 정렬되지 않는 원소를 삽입하기 위해서 왼쪽 원소들을 순차적으로 비교해나간다. 그런데 이진 삽입 정렬은 이미 왼쪽 원소들은 정렬되어있으므로, 이 사실을 기반으로 이진 탐색으로 삽입할 위치를 찾는다.
시간복잡도. 최고 평균 최악
삽입 정렬 O(N) O(N^2) O(N^2)
이진 삽입 정렬.O(NlogN) O(N^2) O(N^2)
직접 소스코드를 돌려 본 결과 시간복잡도로 추측해 본것처럼 최고의 경우에만 조금 빨라질거라는 예상과 달리 최고의 경우에는 약간 느려지고, 나머지 경우에는 약간 빨라졌다.
소스.
# -*- encoding: cp949 -*-
import time
import random
N = 10000
def swap(a,i,j):
a[i],a[j] = a[j],a[i]
def CheckSort(a,n):
Sorted = True
for i in range(n):
if a[i] > a[i+1]:
Sorted = False
if not Sorted:
break
if Sorted: print '정렬 완료.'
else: print '정렬 오류 발생.'
def binary_InsertionSort(a,b,e): #이진 삽입 정렬
for i in range(b+1,e+1):
key = a[i]
l = b-1
r = i
while r-l > 1:
m = l+(r-l)/2
if a[m] > key:
r = m
else: l = m
m = i+1
m -= 1
while m > r:
a[m] = a[m-1]
m -= 1
a[r] = key
def InsertionSort(a,N): #삽입 정렬
for i in range(2,N+1):
v = a[i]
j=i
while a[j-1] > v:
a[j] = a[j-1]
j -= 1
a[j] = v
def main():
a = [random.randint(1,65536) for i in range(0,N+1)] #랜덤한 10000개의 데이터
a[0] = -1
start_time = time.time()
InsertionSort(a,N)
print '(랜덤)삽입 정렬의 실행 시간 (N = {} ) : {}'.format(N,time.time()-start_time)
CheckSort(a,N)
a = [i for i in range(0,N+1)] #정렬된 10000개의 데이터
a[0] = -1
start_time = time.time()
InsertionSort(a,N)
print '(최고)삽입 정렬의 실행 시간 (N = {} ) : {}'.format(N,time.time()-start_time)
CheckSort(a,N)
a = [i for i in range(N,-1,-1)] #최악의 경우의 10000개의 데이터
a[0] = -1
start_time = time.time()
InsertionSort(a,N)
print '(최악)삽입 정렬의 실행 시간 (N = {} ) : {}'.format(N,time.time()-start_time)
CheckSort(a,N)
print
a = [random.randint(1,65536) for i in range(0,N+1)] #랜덤한 10000개의 데이터
a[0] = -1
start_time = time.time()
binary_InsertionSort(a,1,N)
print '(랜덤)이진 삽입 정렬의 실행 시간 (N = {} ) : {}'.format(N,time.time()-start_time)
CheckSort(a,N)
a = [i for i in range(0,N+1)] #정렬된 10000개의 데이터
a[0] = -1
start_time = time.time()
binary_InsertionSort(a,1,N)
print '(최고)이진 삽입 정렬의 실행 시간 (N = {} ) : {}'.format(N,time.time()-start_time)
CheckSort(a,N)
a = [i for i in range(N,-1,-1)] #최악의 경우의 10000개의 데이터
a[0] = -1
start_time = time.time()
binary_InsertionSort(a,1,N)
print '(최악)이진 삽입 정렬의 실행 시간 (N = {} ) : {}'.format(N,time.time()-start_time)
CheckSort(a,N)
if __name__=='__main__':
main()
