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

그림 6-16은 앞의 ‘4-정렬’을 마친 상태에서 2칸만큼 떨어진 요소를 모아 두 그룹({7, 3, 8, 4},
{1, 2, 6, 5})으로 나누어 ‘2-정렬’을 하는 과정입니다. 정렬을 마치고 나면 각각의 그룹은 {3, 4,
7, 8}, {1, 2, 5, 6}으로 정렬됩니다.

7 1 3 2 8 6 4 5
①
7 1 3 2 8 6 4 5
 2칸만큼 떨어진 4개의 요소를 정렬
3 1 4 2 7 6 8 5

② 3 1 4 2 7 6 8 5
 2칸만큼 떨어진 4개의 요소를 정렬
3 1 4 2 7 5 8 6
정렬을 마치지는 않았지만 정렬을 3 1 4 2 7 5 8 6
마친 상태에 가까워집니다.
[그림 6-16] 셸 정렬의 2-정렬

이렇게 해서 얻은 배열은 좀 더 정렬된 상태에 가까워집니다. 마지막으로 ‘1-정렬’을 적용하

면 정렬을 마치게 됩니다.

그림 6-17에 셸 정렬의 전체 흐름을 나타냈습니다. 셸 정렬 과정에서 수행하는 각각의 정렬
을 ‘h–정렬’이라고 합니다. 그림 6-17의 경우 h 값을 4, 2, 1로 감소하면서 7회의 정렬로 정렬

을 마쳤습니다.

1. 2개 요소에 대해 ‘4-정렬’을 합니다(4개의 그룹).
2. 4개 요소에 대해 ‘2-정렬’을 합니다(2개의 그룹).
3. 8개 요소에 대해 ‘1-정렬’을 합니다(1개의 그룹).

a 8 1 4 2 7 6 3 5 h
 4개의 그룹에 대해서 4-정렬을 수행(그림 6-15) 4
b 7 1 3 2 8 6 4 5 
 2개의 그룹에 대해서 2-정렬을 수행(그림 6-16) 2
c 3 1 4 2 7 5 8 6 
 1개의 그룹에 대해서 1-정렬을 수행 1
d 1 2 3 4 5 6 7 8 정렬을 마침

[그림 6-17] 셸 정렬

06•정렬 219