가장 작은 범위를 만든 후 해당 범위에서 가장 작은 수를 왼쪽으로 이동시키고, 점점 범위를 넓혀가며 범위 내에서 작은 수를 점차적으로 왼쪽으로 이동시키는 방법.
말로 설명하기엔 역시나 어려움이 따른다. -_-
하지만 직접 그림을 보거나 코드를 보면 금방 이해가 갈 것이다.
1. 처음에는 가장 최소 단위인 2개의 블록만 범위로 잡는다. 기존의 3이란 값에 8을 비교해야 하는 상황이다.
3과 8을 비교하면 8이 더 크기 때문에 따로 swap이 일어나지 않는다.
2. 범위를 3개로 넓힌다. 0이란 값이 새로 첨가된 상황이다. 0과 8을 비교한다. 0이 더 작기 때문에 0 위치에 8을 집어넣는다.
3. 0을 3과 비교한다. 0이 더 작으므로 0 위치에 3을 집어 넣는다. 범위 마지막 위치이기 때문에 현재 위치에 0 값을 집어 넣는다.
4. 범위를 하나 더 늘린다. 이번에는 2와 8을 비교한다. 2 위치가 8로 교체되고, 2는 3과 비교가 된다.
역시 2위치에 3이 써지고 0과 2를 비교하면 2가 더 크기 때문에 현재 위치에 2을 삽입한다.
이런식으로 정렬을 진행하는 방식이 삽입 정렬이다.
삽입 정렬은 이미 정렬되어 있는 상태에선 가장 빠른 속도를 자랑한다. (이게 무슨 소용??)
하지만 역순으로 정렬을 해야 할 상황이 온다면 가장 최악의 속도를 나타낼 것이다.
