DataStructure in Python[Insert Sort]

출처 : http://onestep.tistory.com/45

       : http://hyeonstorage.tistory.com/268

삽입 정렬(揷入整列, insertion sort)은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.

import random
import time
# python3.4 
# 테스트할 리스트를 만든다.
list = []
 
for i in range(5000):
    list.append(random.randint(1, 50000))
list1 = list.copy()
print(id(list),id(list1))
 
# insert 정렬실행
# while문으로 if와 for을 여기서는 같이 써준다.
def insertSort(intoList):
    start_time = time.time()
    intoList.insert(0,-1)
    for idx2 in range(2,len(intoList)):
        tempIdx = idx2-1
        tempValue = intoList[idx2]
        while intoList[tempIdx] > tempValue:
            intoList[tempIdx + 1] = intoList[tempIdx]
            tempIdx -= 1
        intoList[tempIdx+1] = tempValue
    del intoList[0]
    end_time = time.time()
    print("소요시간",end_time - start_time)
 
print("정렬전 ==>",list)
insertSort(list)
print("정렬후 ==>",list)

  가장 앞에 -1 이라는 원소를 추가했다가 삭제하는 이유는 while문의 조건을 하나로 하기 위함이다. 이런 루틴이 없으면 insert_index가 0보다 큰지도 판별 해야 한다. 이렇게 임시로 값을 넣어서 조건문을 하나 줄이는 기법을 보초 기법 이라고 한다. 현재 구현된 삽입 정렬은 삽입 될 위치를 찾을 때 앞에서 부터 차례대로 찾는 순차 검색을 한다. 검색법 중에 이분 검색을 이용 하면 삽입 할 위치를 빠른 속도로 찾을 수 있다. 삽입 정렬은 이중 루프문으로 구성 되어있기 때문에 O(N^2)의 성능을 가진다.

리스트의 인덱스 0에 -1을 넣어주는데 이것을 넣어주지 않으면 list[-1]값을 비교한다. 이런식으로 조건이 맞으면 -1, -2 인덱스를 전부 비교해 버리기 때문에 0에서 끊을수 있도록 값을 삽입하는 것이다. 값을 삽입하지 않으면 위의 글처럼 index0인지 비교를 해야하는데 이게 알다시피 훨씬 느리게 되기 때문에 좋지 않다.

while문 대신에 for 문과 if문을 같이 쓰면 괜찮지 않겠느냐 하는 생각도 들텐데 while문내의 조건에서 끊는 거랑 for문으로 일단 모든 값을 돌린다음에 그걸 if문에서 스탑시키는거랑 성능차이가 많이 났다. 사실 참조했던 소스에서는 while문 내에 index -1을 하는데 그걸 하지 않도록 index 값을 설정했더니 8%정도 시간이 단축되었다. 20000개 값이 있는 배열을 정리하는데 2초정도 단축되었다. (그래봤자 느리지만..)