[탐색과 정렬] 삽입 정렬

삽입 정렬 (Insertion Sort)

자료의 모든 요소를 이미 정렬된 부분과 비교하여, 자신의 위치를 찾아 삽입하는 방식의 정렬이다. 두 번째 자료부터 시작하여, 그 앞의 자료와 비교하여 삽입할 위치를 지정한 후, 삽입 위치 이후의 자료는 하나씩 뒤로 옮기고, 삽입 위치에 자료를 삽입하여 정렬한다. 아래의 그립으로 쉽게 이해할 수 있다.

이미지 출처 :https://godgod732.tistory.com/12

 

 

계산 복잡도는 선택 정렬과 동일하게 $$ \mbox{O}(n^2) $$

 

 

코드

코드로 표현하면 아래 함수와 같다.

def insertion_sort(list):
    for i in range(1, len(list)):
        for j in range(0, i):
            if list[i] > list[j]:
                list.insert(j, list.pop(i))

    return list

 

 

 

참고 문서

https://godgod732.tistory.com/12