삽입정렬 (Insertion Sort)
삽입정렬은 손안의 카드를 정렬하는 방법과 유사합니다.
즉, 새로운 카드를 기존의 정렬된 카드 사이의 올바른 자리를 찾아 삽입함으로써 정렬이 유지되게 합니다.
- 새로 삽입될 카드의 수 만큼 반복하면 전체 카드가 정렬
1. 리스트의 처음부터 값을 비교하며 정렬된 부분의 어느 위치에 삽입되어야 하는가를 판단
2. 해당 위치에 이 숫자를 삽입하게 되면 정렬된 부분의 크기는 하나씩 커지며 자리이동
3. 정렬되지 않은 부분은 크기가 하나 줄어듦
의 순서를 반복합니다.
삽입정렬의 특징
삽입정렬은 안정성이 있으며, 비효율적입니다. 처리속도는 선택정렬과 마찬가지로 O(n^2)입니다.
삽입정렬 코드
