[CS] 삽입 정렬

 

 

삽입 정렬

 

삽입 정렬은 전체에서 하나씩 올바른 위치에 "삽입" 하는 방식입니다!

선택 정렬은 현재 데이터의 상태와 상관없이 항상 비교하고 위치를 바꾸지만,

 

삽입 정렬은 필요할 때만 위치를 변경하므로 더 효율적인 방식입니다!

이미 키 순으로 정렬된 사람들이 일렬로 쭉~ 서 있는데, 

다음 원소가 그 정렬된 사람들 사이를 비집고 들어가면서

 아 여기가 내 자리구나! 하면서 삽입하며 정렬하는 방식입니다.

 

 

 

아래 [5, 3, 8, 1, 2] 배열을 삽입 정렬하는 그림을 보시면 이해해보겠습니다.

 

 

 

삽입 정렬의 진행순서를 코드로 좀 더 자세히 알아보겠습니다

 

[4, 6, 2, 9, 1]  # 정렬되지 않은 배열

1단계 : [4, 6, 2, 9, 1] 
        4는 현재 정렬되어 있는 부대원입니다. 
			  그럼 이제 새로운 신병인 6을 받습니다.
        4, 6 이 되는데 4 < 6 이므로 그대로 냅둡니다.
       [4, 6, 2, 9, 1] 이렇게요!

자, 그러면 이제 한 바퀴를 돌렸죠?
이 과정에서 새로운 부대원인 4, 6은 현재 정렬된 상태입니다!
이처럼, 삽입 정렬은 한 바퀴가 돌 때마다 정렬된 상태가 됩니다.
끝까지 한 번 반복해볼게요!

2단계 : [4, 6, 2, 9, 1]
        4, 6 은 현재 정렬되어 있는 부대원입니다.
        그럼 이제 새로운 신병인 2를 받습니다.
        4, 6, 2 가 되는데 6 > 2 이므로 둘을 변경합니다!
        4, 2, 6 가 되는데 4 > 2 이므로 둘을 변경합니다!
       [2, 4, 6, 9, 1] 이렇게요!

3단계 : [2, 4, 6, 9, 1]
        2, 4, 6 은 현재 정렬되어 있는 부대원입니다.
        그럼 이제 새로운 신병인 9를 받습니다.
        2, 4, 6, 9 가 되는데 6 < 9 이므로 그대로 냅둡니다.
       [2, 4, 6, 9, 1] 이렇게요!

4단계 : [2, 4, 6, 9, 1]
        2, 4, 6, 9 은 현재 정렬되어 있는 부대원입니다.
        그럼 이제 새로운 신병인 1을 받습니다.
        2, 4, 6, 9, 1 가 되는데 9 > 1 이므로 둘을 변경합니다!
        2, 4, 6, 1, 9 가 되는데 6 > 1 이므로 둘을 변경합니다!
        2, 4, 1, 6, 9 가 되는데 4 > 1 이므로 둘을 변경합니다!
        2, 1, 4, 6, 9 가 되는데 2 > 1 이므로 둘을 변경합니다!
       [1, 2, 4, 6, 9] 이렇게요!

자, 모두 정렬이 되었습니다! 어떠신가요? 감이 좀 오시나요?

 

 

 

구현

 

def insertionsort(lst):
    # 0번째 요소는 이미 정렬되어있으니, 1번째 ~ lst(len)-1 번째를 정렬하면 된다.
    for cur in range(1, len(lst)):
        # 비교지점이 cur-1 ~ 0(=cur-cur)까지 내려간다.
        for delta in range(1, cur + 1):
            cmp = cur - delta
            if lst[cmp] > lst[cmp + 1]:
                lst[cmp], lst[cmp + 1] = lst[cmp + 1], lst[cmp]
            else:
                break
    return lst