정렬 방법론.
1. 0번째는 값이 맞는지 키값으로 사용하기 위해 -1처럼 가장 작은 값으로 둔다.
2. ~1번째까지와 2번째를 비교해서 2번째 원소가 들어갈 자리를 ~1번까지중 만든다음 2번째 원소를 집어넣는다.
3. ~2번째까지와 3번째를 비교해서 ~~~ 나머지 동일.
4. 끝까지 간다.
특징.
1. 계속 비교하므로 리스트 크기가 크면 불리하다. (버블과 비슷)
2. 정렬이 거의 된 데이터일 경우 더 유리하다.(교환이 적게 일어나므로) (버블과 비슷)
3. 데이터가 역순인경우, 즉 최악의경우에 시간이 엄청 느리다. (버블과 비슷)
4. 버블정렬과 다른점은 버블정렬은 n번째와 n+1번째만 비교해서 자리를 바꾸지만 삽입 정렬은 n+1번째의 데이터를 0~n번째까지중 어디에 들어가야할지 자리를 찾아서 집어넣는다는것.
시간 복잡도는 O(n^2).
10000개의 데이터를 돌린 결과.
버블정렬과 비슷하게 분포를 보이지만 특이한 점은 이미 정렬됬을 경우 극단적으로 짧게 시간이 걸린다는 점. 이미 정렬된 배열의 경우에 유리하다.
# -*- 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 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)
if __name__=='__main__':
main()
근데 또 희한한점은 요렇게 함수를 바꾸면 최악의 경우던 랜덤의 경우던 다 빨라진다는 거다.
매번 반복문마다 변수 v를 할당하는게 오버해드가 그리 큰듯 싶다
def InsertionSort(a,N):
for i in xrange(2,N+1):
j = i
while a[j-1] > a[i]:
a[j] = a[j-1]
j -= 1
a[j] = a[i]