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

정렬되지 않은 상태의 배열(그림 6-17의 a )에 대해 단순 삽입 정렬을 그냥 적용하는 것이 아

니라 ‘4-정렬’, ‘2-정렬’로 조금이라도 정렬이 된 상태에 가까운 배열( c )로 만들어 놓은 다
음에 마지막으로 단순 삽입 정렬을 수행하여 정렬을 마칩니다. 이렇게 여러 개의 그룹으로 나
누어 정렬하는 이유는 단순 삽입 정렬의 장점은 살리고 단점은 보완하기 위해서입니다. 정렬
해야 하는 횟수는 늘지만 전체적으로는 요소 이동의 횟수가 줄어들어 효율적인 정렬을 할 수

있습니다. 단순 삽입 정렬의 장점과 단점은 06-5절의 앞부분(217쪽)에 정리해 두었습니다.

실습 6-6은 셸 정렬 프로그램의 한 예입니다.

실습 6-6 •완성 파일 chap06/shell1.c

01 /* 셸 정렬 */
실행 결과
02 #include <stdio.h>
셸 정렬
03 #include <stdlib.h>
요소 개수 : 7
04 x[0] : 22
05 /*--- 셸 정렬 함수 ---*/ x[1] : 5
06 void shell(int a[], int n) x[2] : 11
07 { x[3] : 32
x[4] : 120
08 int i, j, h;
x[5] : 68
09 for(h = n / 2; h > 0; h /= 2)
x[6] : 70
10 for(i = h; i < n; i++) { 오름차순으로 정렬했습니다.
11 int tmp = a[i]; x[0] = 5
12 for(j = i - h; j >= 0 && a[j] > tmp; j -= h) x[1] = 11
13 a[j + h] = a[j]; x[2] = 22
x[3] = 32
14 a[j + h] = tmp;
x[4] = 68
15 }
x[5] = 70
16 } x[6] = 120
17
18 int main(void)
19 {
20 int i, nx;
21 int *x; /* 배열의 첫 번째 요소에 대한 포인터 */
22 puts("셸 정렬");
23 printf("요소 개수 : ");
24 scanf("%d", &nx);
25 x = calloc(nx, sizeof(int));
26 for(i = 0; i < nx; i++) {
27 printf("x[%d] : ", i);
28 scanf("%d", &x[i]);

220 C 알고리즘