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

29 }
30 shell(x, nx); /* 배열 x를 셸 정렬 */
31 puts("오름차순으로 정렬했습니다.");
32 for(i = 0; i < nx; i++)
33 printf("x[%d] = %d\n", i, x[i]);
34 free(x); /* 배열을 해제 */
35
36 return 0;
37 }

단순 삽입 정렬을 수행하는 부분(초록색 박스로 표시한 부분)은 실습 6-5와 거의 같습니다. 차이점은 선택한 요소와 비교
하는 요소가 서로 이웃하지 않고 h칸만큼 떨어져 있다는 것입니다.

증분값(h 값)의 선택

앞에서는 h 값을 아래처럼 변화시켰습니다.

h = 4, 2, 1

h 값은 n부터 감소하여 마지막에 1이 되면 됩니다. 그러면 h 값을 어떤 수열로 감소해야 좀 더
효율적으로 정렬할 수 있을까요? 실제로 어떤 수열이 알맞을까요? 앞에서 했던 ‘배열을 그룹

으로 나누는 과정’을 다시 살펴보겠습니다.

a
8 1 4 2 7 6 3 5

b c
8 7
7 3 8 4
1 6
4 3
1 2 6 5
2 5

4-정렬 × 4 2-정렬 × 2

[그림 6-18] 셸 정렬의 그룹 분할 과정(h = 4, 2, 1)

여기서는 a 가 학생 8명의 점수를 나타내고 있다고 가정합시다. 먼저 b 처럼 학생을 2명씩
4개의 그룹으로 나누어 정렬하고 c 처럼 학생을 4명씩 2개의 그룹으로 나누어 다시 정렬합

06•정렬 221