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

19 실행 결과
20 int main(void)
셸 정렬
21 { 요소 개수 : 7
22 int i, nx; x[0] : 22
23 int *x; /* 배열의 첫 번째 요소에 대한 포인터 */ x[1] : 5
24 x[2] : 11
x[3] : 32
25 puts("셸 정렬");
x[4] : 120
26 printf("요소 개수 : ");
x[5] : 68
27 scanf("%d", &nx); x[6] : 70
28 x = calloc(nx, sizeof(int)); 오름차순으로 정렬했습니다.
29 x[0] = 5
30 for(i = 0; i < nx; i++) { x[1] = 11
x[2] = 22
31 printf("x[%d] : ", i);
x[3] = 32
32 scanf("%d", &x[i]);
x[4] = 68
33 } x[5] = 70
34 shell(x, nx); /* 배열 x를 셸 정렬 */ x[6] = 120
35
36 puts("오름차순으로 정렬했습니다.");
37 for(i = 0; i < nx; i++)
38 printf("x[%d] = %d\n", i, x[i]);
39 free(x); /* 배열을 해제 */
40
41 return 0;
42 }

1 은 h의 초깃값을 구합니다. 1부터 시작하여 값을 3배하고 1을 더하면서 n / 9를 넘지 않는
가장 큰 값을 h에 대입합니다.
2 가 버전 1과 다른 점은 h의 값이 변하는 방법입니다(h 값을 3으로 나눕니다). 반복하여 마지막
에 h의 값은 1이 됩니다. 셸 정렬의 시간 복잡도는 O(n 1.25 )으로, 이는 기존의 시간 복잡도인

O(n )에 비해 매우 빠릅니다. 그러나 이 알고리즘도 멀리 떨어져 있는 요소를 교환해야 하므
2
로 안정적이지는 않습니다.

연습 Q12 요소의 이동 횟수를 계산할 수 있도록 버전 1과 버전 2를 수정한 프로그램을 작성하세요.
문제 여러 가지 배열을 입력하고 프로그램을 실행하며 이동 횟수를 비교해 보세요.

06•정렬 223