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

다시 말해 tmp에 a[i]를 대입(3을 선택)하고 반복 제어용 변수 j에 i - 1을 대입한 다음 아래의

두 조건 중 하나를 만족할 때까지 j를 1씩 감소하면서 대입하는 작업을 반복합니다.

1. 정렬된 열의 왼쪽 끝에 도달합니다.
2. tmp보다 작거나 같은 key를 갖는 항목 a[j]를 발견합니다.

이때 드모르간 법칙(보충수업 1-7)을 적용하면 아래의 두 조건이 모두 성립할 때까지 반복한다
고 할 수 있습니다.

1. j가 0보다 큽니다.
2. a[j - 1] 값이 tmp보다 큽니다.

이 과정을 마치고 난 다음에 요소 a[j]에 tmp를 대입하면 한 요소에 대한 단순 삽입 정렬을 마
치게 됩니다.

실습 6-5는 단순 삽입 정렬 프로그램의 예입니다.

•완성 파일 chap06/insertion.c
실습 6-5
01 /* 단순 삽입 정렬 */
실행 결과
02 #include <stdio.h>
단순 삽입 정렬
03 #include <stdlib.h>
요소 개수 : 7
04 x[0] : 22
05 /*--- 단순 삽입 정렬 함수 ---*/ x[1] : 5
06 void insertion(int a[], int n) x[2] : 11
07 { x[3] : 32
x[4] : 120
08 int i, j;
x[5] : 68
09 for(i = 1; i < n; i++) {
x[6] : 70
10 int tmp = a[i]; 오름차순으로 정렬했습니다.
11 for(j = i; j > 0 && a[j - 1] > tmp; j--) x[0] = 5
12 a[j] = a[j - 1]; x[1] = 11
13 a[j] = tmp; x[2] = 22
x[3] = 32
14 }
x[4] = 68
15 }
x[5] = 70
16 x[6] = 120
17 int main(void)
18 {

214 C 알고리즘