- 이미 정렬되어 있는 데이터 범위 내에서 정렬되지 않은 데이터를 적절한 위치에 삽입시켜서 정렬하는 방식.
- 시간 복잡도 O(n^2)
수행방식
- 현재 대상의 데이터값을 선택한다.(다음으로 정렬할 데이터 index 위치, 아직 정렬되지 않은 첫번째 값)
- 아래의 2번째 삽입 기준으로하면 1번째 인덱스가 대상.
- 정렬된 데이터 범위내에서 선택된 데이터가 삽입될 위치를 탐색함.
- 이진탐색 활용하면 좋음
- 삽입위치부터 인덱스(현재 대상의 데이터값)에 있는 위치까지 shift연산을 진행함.
- 삽임위치에 선택한 데이터를 삽입하고, 인덱스의 위치를 한칸 +
- 전체 데이터의 크기만큼 index가 커질때까지(선택할 데이터가 없을때까지 반복)
2번째 삽입
1. 1번째 데이터는 42(이미 정렬되어있다고 가정)
2. 2번째 데이터 삽입시 42가 정렬데이터 범위내로 가정
3. 32 선택
| 42 | 32 | 24 | 60 | 40 |
3. 32와 42랑 비교했을때 정렬하려면 42를 2번째로 옮기고, 32를 맨앞으로 삽입
| 32 | 42 | 24 | 60 | 40 |
3번째 삽입
1. 정렬된 데이터는 32, 42까지가 됨
| 32 | 42 | 24 | 60 | 40 |
2. 24의 위치를 찾고, 맨앞이 대상위치이므로, 32, 42 한칸씩 오른쪽으로 옮기고 24 맨앞으로
| 24 | 32 | 42 | 60 | 40 |
4번째 삽입
1. 정렬된 데이터는 24, 32, 42까지가 됨
| 24 | 32 | 42 | 60 | 40 |
2. 60 의 위치를 찾고, 현재위치가 대상위치이므로, 그대로 둠
5번째 삽입
1. 정렬된 데이터는 24, 32, 42,60까지가 됨
| 24 | 32 | 42 | 60 | 40 |
2. 40의 적절한 위치를 찾고, 중간이 대상위치이므로, 42,60을 한칸씩 옮기고 40 가운데로
| 24 | 32 | 40 | 42 | 60 |