모두의 알고리즘 문제 09. 삽입 정렬

def find_ins_idx(r, v): #리스트r, 삽입값v. v가 들어갈 위치를 돌려주는 함수
    #이미 정렬된 리스트r의 자료를 앞에서부터 차례로 확인하며
    for i in range(0, len(r)):
        if v < r[i]: #삽입값v가 r[i]보다 작으면 i를 반환해서 r[i]보다 앞에 v를 삽입.
            #r[i]앞에 v를 놓아야 정렬 순서가 유지된다
            return i # i자리에 값을 삽입하면 기존의 i자리의 값은 한자리 뒤로 밀려남.
    #적절한 위치 못찾은거면 모든 자료보다 삽입값이 큰거니까 제일 뒤에 삽입
    return len(r)

def ins_sort(a):
    result = [] #새 리스트 만들기. 결과 저장
    while a: #리스트 a에 값이 남아있을 때까지 반복
        value = a.pop(0) # 삽입값value. 기존 리스트 첫 위치에서 하나 꺼냄.
        #pop을 사용해서 기존 리스트에선 value값이 지워짐.
        ins_idx = find_ins_idx(result, value) #값이 들어갈 위치 탐색
        result.insert(ins_idx, value) #값을 삽입. n번 자리에 넣으면 기존 n번자리의 값은 한칸 뒤로 밀려남
    return result




def insert_sort(a):
    n=len(a)
    for i in range(1, n): # 1부터 n-1까지
        key=a[i] #i번 위치에 있는 값을 key에 저장
        j=i-1 #j를 i 바로 왼쪽 위치에 저장
        #리스트의 j번 위치에 있는 값과 key를 비교해 key가 삽입될 적절한 위치를 찾음
        while j>=0 and a[j] > key:
            a[j+1]= a[j] #삽입할 공간이 생기도록 값을 오른쪽으로 한칸 이동
            j-=1
        a[j+1] = key #찾은 삽입 위치에 key를 저장

d = [2, 4, 5, 1, 3]
print(ins_sort(d))

d = [2, 4, 5, 1, 3]
insert_sort(d)
print(d)

이해하기 쉽게 설명한 알고리즘은 find_ins_idx와 ins_sort이고 일반적인 삽입 정렬 알고리즘은 insert_sort이다.

 

코드가 어떻게 동작하는지 완전히 이해하는건 시간이 좀 걸렸다.

 

시간복잡도에 대해서 알아보자. 이미 정렬이 끝난 [1, 2, 3, 4, 5]같은 리스트를 집어넣으면 O(n)의 계산복잡도로 정렬을 마치겠지만 일반적인 입력이라면 삽입정렬의 계산복잡도는 O(n^2)이다.

 

따라서 선택정렬과 마찬가지로 정렬할 입력 크기가 크면 정렬하는데 굉장히 오래 걸린다.

 

 

 

 

 

insert_sort의 동작 과정을 정리해보겠다.

 

리스트의 i위치를 키값, i의 왼쪽을 j라고 이름붙이고 키값과 비교해서 어느 자리에 들어가야할지 탐색한다.

 

위의 코드 중 while j>=0 and a[j] > key: 부분은 키값과 a[j]를 비교해 키값이 더 크다면 다음 바퀴로 넘어간다.

 

 

[2 | 4 5 1 3]   key=4, a[j]=2

 

[2 4 | 5 1 3]   key=5, a[j]=4

 

 

만약 while j>=0 and a[j] > key: 부분에서 키값이 더 작다면 키값의 위치인 a[j + 1]위치에 a[j]를 넣는다. 이때 a[j+1]의 기존 값은 이미 키값으로 빼둔 상태이다. 왼쪽보다 오른쪽의 값이 더 작으니 값을 왼쪽에서 오른쪽으로 옮겨주는 과정이라 보면 된다.

 

 

[2 4 5 | 1 3]   key=1, a[j]=5

 

[2 4 5 | 5 3]   a[j+1] = a[j], j=j-1

 

 

이후 j=j-1문으로 j를 왼쪽으로 한칸 옮긴다. 이때 a[j]가 또 키값보다 크다면 a[j]는 a[j+1]로 이동한다.

 

 

[2 4 5 | 5 3]   a[j]=4, key=1

 

[2 4 4 | 5 3]   a[j]=2, key=1

 

 

그 후 j는 값이 1 줄어서 아까보다 한칸 왼쪽의 값을 키와 비교한다. j는 0이었는데 값이 1 줄어들어서 -1이 된다.

 

 

[2 2 4 | 5 3]   j = -1, key=1

 

 

j가 반복문 while j>=0 and a[j] > key: 조건의 조건을 불충족해서 반목문을 탈출한다.

 

 

[1 2 4 | 5 3]   j=-1인 상황에서 a[j+1] = key문에 의해 a[0]에 key가 삽입

 

for문의 3번째 바퀴가 끝나고 4번째 바퀴가 시작된다.

 

이런식으로 코드가 진행되고, for문이 끝날 땐 오름차순으로 리스트가 정렬된다.