삽입 정렬이란?
정렬 범위를 1칸씩 확장해나가면서 새롭게 정렬 범위에 들어온 값을 기존 값들과 비교하여 알맞은 자리에 꼽아주는 알고리즘.
1부터 5까지 총 5개의 숫자가 들어있는 배열에 있다고 가정하자.
[2, 1, 5, 4, 3]
맨 처음에는 첫번 째 2개의 값만 정렬 범위에 포함시키고 생각한다. 앞에 있는 값 2는 뒤에 있는 값 1보다 작기 때문에 서로 자리를 바꿔준다.
[2, 1] : 2 > 1 => swap
[1, 2]
* *
그 다음에는 기존의 정렬 범위에 한칸 확장하여 세번 째 값을 추가시키고 생각해본다. 기존 정렬 범위에서 가장 큰 값인 2와 새롭게 추가된 5를 비교하면 자리를 바꿀 필요가 없다는 것을 알 수 있다. 기존에 정렬 범위에 있던 두 개의 값은 이 전 패스에서 이미 정렬되어 있기 때문에 굳이 1과 5를 비교할 필요가 없다.
[1, 2, 5]: 2 < 5 => OK
[1, 2, 5]
* * *
다음 패스에서는 정렬 범위를 한 칸 더 확장하여 4번 째 값을 추가시키고 생각해볼 차례이다. 기존 정렬 범위에서 가장 큰 값인 5와 새롭게 추가된 4를 비교하면, 앞에 있는 값이 뒤에 있는 값보다 크기 때문에 서로 자리를 바꿔야 한다. 이제 기존 정렬 범위에서 두 번째로 큰 값인 2와 방금 자리를 교체 당한 4를 비교해보면 더 이상 자리를 바꿀 필요가 없다는 것을 알 수 있다.
[1, 2, 5, 4]: 5 > 4 => swap
[1, 2, 4, 5]: 2 < 4 => OK
[1, 2, 4, 5]
* * * *
마지막 패스에서는 정렬 범위를 전체로 확장하여 마지막 값까지 포함한다. 여태까지 했던 방식과 동일하게 새로 추가된 값과 기존에 있던 값들을 뒤에서부터 비교해가면서 2번의 자리 교체가 필요하다는 것을 알 수 있다.
[1, 2, 4, 5, 3]: 5 > 3 => swap
[1, 2, 4, 3, 5]: 4 > 3 => swap
[1, 2, 3, 4, 5] : 2 < 3 => OK
[1, 2, 3, 4, 5]
* * * * *
