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

셸 정렬

셸 정렬(shell sort)은 단순 삽입 정렬의 장점(ⓐ)은 살리고 단점(ⓑ)은 보완한 정렬 알고리즘으
로, 도널드 셸(D. L. Shell)이 고안했습니다. 먼저 정렬할 배열의 요소를 그룹으로 나눠 각 그룹
별로 단순 삽입 정렬을 수행하고, 그 그룹을 합치면서 정렬을 반복하여 요소의 이동 횟수를

줄이는 방법입니다.
다음 절에서 살펴볼 퀵 정렬이 고안되기 전까지는 가장 빠른 알고리즘으로 알려져 있었습니다.

그림 6-15의 배열을 예로 들어 알고리즘을 살펴보겠습니다. 먼저 배열을 4개의 그룹({8, 7},
{1, 6}, {4, 3}, {2, 5})으로 나누고 각 그룹별로 정렬합니다. ①은 {8, 7}을 정렬하여 {7, 8}로, ②는

{1, 6}을 정렬하여 {1, 6}으로, ③은 {4, 3}을 정렬하여 {3, 4}로, ④는 {2, 5}를 정렬하여 {2, 5}
로 정렬된 상태입니다.

이렇게 4칸만큼 떨어진 요소를 모아 그룹을 4개로 나누어 정렬하는 방법을 ‘4–정렬’이라고

합니다. 아직 정렬을 마친 상태는 아니지만 정렬을 마친 상태에 가까워집니다.

8 1 4 2 7 6 3 5

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

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

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

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

정렬을 마치지는 않았지만 정렬을 7 1 3 2 8 6 4 5
마친 상태에 가까워집니다.

[그림 6-15] 셸 정렬의 4–정렬

218 C 알고리즘