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

니다. 여기서 b 의 2개의 그룹을 각각 합치면 c 의 그룹이 됩니다. 즉, ‘초록색 그룹’과 ‘회색

그룹’은 서로 섞이지 않습니다. 그런데 이렇게 그룹이 섞이지 않으면 c 를 합쳤을 때 다시 처
음 단계인 a 와 동일한 상태가 됩니다. 그러면 다시 a 의 학생을 정렬하는 것과 같아서 기껏
그룹을 나누었음에도 정렬 알고리즘이 동작하지 않습니다. c 가 a 와 동일한 상태라는 말은 그룹
의 구성 요소가 같다는 뜻입니다.

이런 문제를 해결하기 위해서는 h 값이 서로 배수가 되지 않도록 해야 합니다. 이렇게 하면 요
소가 충분히 섞여 효율적인 정렬을 기대할 수 있습니다. 다음의 수열을 사용하면 셸 정렬 알
고리즘을 간단하게 만들 수 있을 뿐만 아니라 효율적인 결과도 얻을 수 있습니다.

h = …, 121, 40, 13, 4, 1

이 수열을 거꾸로 살펴보면 1부터 시작하여 3배한 값에 1을 더하는 수열이라는 것을 알 수 있
습니다. 또 h의 초깃값은 너무 크면 효과가 없기 때문에 배열의 요소 개수 n을 9로 나눈 값을
넘지 않도록 정해야 합니다.

실습 6-7은 이 수열을 사용하여 셸 정렬을 수행하는 프로그램입니다.

실습 6-7 •완성 파일 chap06/shell2.c
01 /* 셸 정렬(버전 2 : h = …, 13, 4, 1) */
02 #include <stdio.h>
03 #include <stdlib.h>
04
05 /*--- 셸 정렬 함수(버전 2 : h = …, 13, 4, 1) ---*/
06 void shell(int a[], int n)
07 {
08 int i, j, h;
09 for(h = 1; h < n / 9; h = h * 3 + 1)
1
10 ;
11 for(; h > 0; h /= 3)
12 for(i = h; i < n; i++) {
2
13 int tmp = a[i];
14 for(j = i - h; j >= 0 && a[j] > tmp; j -= h)
15 a[j + h] = a[j];
16 a[j + h] = tmp;
17 }
18 }

222 C 알고리즘