Page 212 - Do it! 자료구조와 함께 배우는 알고리즘(C 언어, 3쇄)

06-4 단순 삽입 정렬

단순 삽입 정렬(straight insertion sort)은 선택한 요소를 그보다 더 앞쪽의 알맞은 위치에 ‘삽입
하는’ 작업을 반복하여 정렬하는 알고리즘입니다. 단순 선택 정렬과 비슷하게 보일 수 있지만
단순 선택 정렬은 값이 가장 작은 요소를 선택해 알맞은 위치로 옮긴다는 점이 다릅니다.

단순 삽입 정렬

단순 삽입 정렬은 트럼프 카드를 한 줄로 늘어놓을 때 사용하는 방법과 비슷한 방법의 알고리
즘입니다. 아래의 배열을 예로 들어 살펴보겠습니다.

6 4 1 7 3 9 8

단순 삽입 정렬은 2번째 요소부터 선택하여 진행합니다. 이때 4는 6보다 앞쪽에 위치해야 하
므로 앞쪽에 삽입합니다. 이 상태에서 6을 오른쪽으로 밀면 아래처럼 됩니다.

4 6 1 7 3 9 8

다음에 3번째 요소 1을 선택해 앞쪽에 삽입합니다. 그 이후에도 계속해서 같은 작업을 수행합
니다. 그림 6-12에서 볼 수 있듯이 정렬된 부분과 아직 정렬되지 않은 부분에서 배열이 다시
구성된다고 생각하면서 아래의 작업을 n - 1회 반복하면 정렬을 마치게 됩니다.

아직 정렬되지 않은 부분의 첫 번째 요소를 정렬된 부분의 알맞은 위치에 삽입합니다.

212 C 알고리즘