삽입정렬 (Insertion Sort)

삽입정렬 (Insertion Sort)

삽입정렬은 손안의 카드를 정렬하는 방법과 유사합니다.

즉, 새로운 카드를 기존의 정렬된 카드 사이의 올바른 자리를 찾아 삽입함으로써 정렬이 유지되게 합니다.

- 새로 삽입될 카드의 수 만큼 반복하면 전체 카드가 정렬

1. 리스트의 처음부터 값을 비교하며 정렬된 부분의 어느 위치에 삽입되어야 하는가를 판단

2. 해당 위치에 이 숫자를 삽입하게 되면 정렬된 부분의 크기는 하나씩 커지며 자리이동

3. 정렬되지 않은 부분은 크기가 하나 줄어듦

의 순서를 반복합니다.

삽입정렬의 특징

삽입정렬은 안정성이 있으며, 비효율적입니다. 처리속도는 선택정렬과 마찬가지로 O(n^2)입니다.

삽입정렬 코드

출처 : http://wonjayk.tistory.com/218