알고리즘 with 파이썬 (2)- 삽입정렬

삽입정렬은 리스트의 두번째 인덱스 list[1] 부터 시작한다.

list[n]일때 list[n-1], list[n-2], list[n-3]...순으로비교하며 자기보다 큰 값과 자리를 바꿔나가는 방식. (오름차순의 경우)

더 작은 값이 나오지 않으면 그자리에 삽입하고 다음 턴으로 넘어간다.

 

선택정렬과 같은 O(n²)의 복잡도를 가지며, 입력값이 크면 시간이 굉장히 오래 걸린다. 

def ins_sort(a):
    n = len(a)
    for i in range(1,n):
        temp = a[i]      # i번 위치에 있는 값을 temp에 저장
        j = i-1         # i 바로 전 인덱스 j에 저장
        while j >=0 and a[j] > temp:
            a[j+1] = a[j] # i 자리에 j 인덱스값 이동
            j -= 1
        a[j+1] = temp # 찾은 삽입 위치에 key 를 저장

heights = [164,158,182,179,162,155,184,171]
ins_sort(heights)
print(heights)

 

* while j >=0 and a[j] > temp:

1씩 감소하는 j 인덱스의 값이 temp 보다 작으면 그 옆자리(a[j+1])가 temp 가 들어갈 자리이기 때문에 반복을 탈출한다.