숫자를 '적절한 위치'에 삽입해보면 어떨까?
다른 정렬들은 무조건 위치를 바꾸는 방식이었다면 삽입 정렬은 필요할 떄만 위치를 변경합니다.
위의 글들을 보면 ‘적절한 위치’,’필요할 때’ 같은 글 때문에 제대로 이해가 안됩니다.
예시를 보면 이해에 도움이 됩니다.
<작동방식>
맨 처음부터 시작하여 각 원소를 차례대로 확인합니다.
현재 확인하는 원소가 이미 정렬된 리스트의 마지막 원소보다 크면, 삽입할 위치를 찾습니다.
삽입할 위치를 찾으면, 그 위치부터 마지막 원소까지 한 칸씩 뒤로 이동시킵니다.
빈 공간에 현재 확인하는 원소를 삽입합니다.
<예시>
1. “1”은 가장 앞에 있기 때문에 삽입할 공간이 없습니다.
2. “10”은 1과 비교해서 a,b 중 ‘적절한 위치’에 삽입하면 됩니다. (b에 삽입합니다.)
3. “5”는 1과 10을 비교하며 a,b,c 중 ‘적절한 위치’에 삽입하면 됩니다. (b에 삽입합니다.)
4. 4, “8”는 1과 5와 10을 비교하며 a,b,c,d 중 ‘적절한 위치’에 삽입하면 됩니다. (c에 삽입합니다.)
이를 계속 반복합니다.
