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

０ １ ２ ３ ４ ５ ６
6 4 1 7 3 9 8
정렬되지 않은 부분의 첫 번째 요소를 정렬
된 열의 ‘알맞은 위치에 삽입’하는 작업을
n-1회 반복합니다. 4 6 1 7 3 9 8
정렬되지 않은 부분의 첫 번째 요소
1 4 6 7 3 9 8

1 4 6 7 3 9 8
정렬된 부분 정렬되지 않은 부분
정렬된 부분 a[0], a[1], …, a[i - 1] 1 3 4 6 7 9 8
정렬되지 않은 부분 a[i], a[i + 1], …, a[n - 1]
1 3 4 6 7 9 8

1 3 4 6 7 8 9
[그림 6-12] 단순 삽입 정렬 과정

i를 1, 2, …, n – 1로 1씩 증가하면서 인덱스가 i인 요소를 꺼내 알맞은 곳에 삽입합니다. 알고

리즘의 개요는 아래와 같습니다.

for(i = 1; i < n; i++) {
//tmp ← a[i]
//a[0], …, a[i - 1]의 알맞은 곳에 tmp를 삽입합니다.
}

그런데 C 언어에는 ‘배열의 요소를 알맞은 위치에 삽입합니다’라는 명령이 없습니다. ‘알맞
은 위치에 삽입’이라는 말이 무슨 의미인지 알아보겠습니다. 그림 6-13은 값이 3인 요소를

선택해 앞쪽의 알맞은 위치에 삽입하는 과정입니다. 앞에서 살펴봤듯이 왼쪽에 이웃한 요소
(7)가 선택한 요소(3)보다 크면 그 값을 대입하고 앞으로 이동하면서 이 작업을 반복합니다(①
~③). 그러다가 선택한 값(3) 이하의 요소(1)를 만나면 그보다 앞쪽은 검사할 필요가 없으므로
해당 위치에 삽입할 값(3)을 대입합니다.

1 4 6 7 3 9 8
①~③ … 3보다 작은 요소를 만날 때까지 ①
이웃한 왼쪽의 요소를 대입하는
작업을 반복합니다. 1 4 6 7 7 9 8
④ … 멈춘 위치에 3을 대입합니다. ②
1 4 6 6 7 9 8
③
1 3 4 6 7 9 8
④
[그림 6-13] 단순 삽입 정렬에서 요소 3의 삽입 과정

06•정렬 213