셸 정렬 (Shell Sort)

개요
정렬 방식
분석
로버트 세지윅의 조언
함께 읽기
참고문헌
주석

개요

삽입 정렬 알고리즘이 항목들을 한 번에 한 자리씩만 이동한다면 평균 시간은 잘 해야 $N^2$ 에 비례할 것이다. 정렬 공정 도중에 각 레코드가 평균적으로 약 $\frac{ 1 }{ 3 } N$ 개의 위치들을 옮겨 다녀야 하기 때문이다. 따라서, 직접 삽입을 크게 개선하기 위해서는 짧은 간격이 아니라 긴 간격으로 레코드들을 이동하는 어떤 메커니즘이 필요하다.

그런 방법 하나가 셸(Donald L. Shell)에 의해서 1959년에 제안되었는데, 제안자의 이름을 따서 셸 정렬(shellsort)이라고 부르게 되었다.¹
TAOCP 3권. 5.2장. 112쪽. ↩ ↩²

셸 정렬은 삽입 정렬에 기반을 둔 빠른 정렬이다.^{2
알고리즘 [개정4판]. 2장. 257쪽. ↩}
셸 정렬을 '점감하는 증분 정렬(diminishing increment sort)'라고 부르기도 한다.^{1
TAOCP 3권. 5.2장. 112쪽. ↩ ↩²}

정렬 방식

셸 정렬은 보조 증분 수열을 사용해 정렬을 한다.

보조 증분 수열은 다음과 같은 특징을 갖는, 1을 향해 감소하는 자연수열이다.

\begin{aligned} h_{t - 1}, h_{t - 2}, . . ., h_{0} \\ h_{0} = 1 \end{aligned}

$\begin{align} & h_{t-1}, h_{t-2}, ..., h_{0} \\ & h_0 = 1 \\ \end{align}$

셸 정렬은 삽입 정렬을 확장한 버전이라 할 수 있다.

삽입 정렬이 바로 옆에 있는 항목끼리만 교환한다면, 셸 정렬은 $h_n$ 만큼 떨어진 항목끼리 교환한다.

다음 이미지는 TAOCP 3권에 실려 있는 예제이다.³

TAOCP 3권. 5.2장. 113쪽. ↩

이 예제는 보조 증분 수열로 $8, 4, 2, 1$ 을 사용하고 있다.

꽤 복잡해 보이지만 잘 살펴보면 각 단계마다 보조 증분 수열의 단계 값에 해당하는 만큼만 이동하고 있음을 알 수 있다.

다음은 위의 정렬 대상 중 가장 큰 숫자인 908의 이동만을 나타낸 것이다. 908이 아닌 숫자는 908과 자리를 바꾸게 되는 수이다.

^      |   |   |   |   |908|   |   |   |   |   |   |   |612|   |   |   |   |   | 908 <-> 612
sort |   |   |   |   |   |   |   |   |653|   |   |   |908|   |   |   |   |   |
sort |   |   |   |   |   |   |   |   |   |   |   |   |   |   |908|   |897|   | 908 <-> 897
sort |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |908|703| 908 <-> 703
sort |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |908|

분석

셸 정렬은 삽입 정렬과 같이 두 아이템의 자리를 바꾸는 방식을 쓰기 때문에, 추가적인 메모리를 거의 쓰지 않는다.

셸 정렬은 어떤 증분 수열을 사용하는지에 따라 정렬 시간이 달라진다.

그런데, 큰 $N$ 값에 대한 최적의 증분 수열을 결정하는 방법은 아직 밝혀지지 않았다고 한다.⁴

TAOCP 3권. 5.2장. 114쪽. ↩

증분 수열 설정에 따라 $O(N^{4 \over 3})$ 의 실행 시간이 나오기도 한다.

$h_s = \begin{cases} 9 \cdot 2^s - 9 \cdot 2^{s / 2} + 1, & \text{if $s$ is even;} \\ 8 \cdot 2^s - 6 \cdot 2^{(s+1) / 2} + 1, & \text{if $s$ is odd.} \end{cases}$
세지윅은 이 $(h_0, h_1, h_2, ...) = (1,5,19,41,109,209,...)$ 증분들을 사용할 때 최악의 경우 실행 시간이 $O(N^{4/3})$ 임을 증명했다.⁵
TAOCP 3권. 5.2장. 124쪽. ↩

세지윅의 책도 읽어보자.

셸-정렬에서 무작위 입력에 대한 평균적인 비교 횟수가 어떻게 되는지 수학적인 결론은 나와 있지 않다. 최악 조건 비교 횟수가 $N^{4/3}, N^{5/4}, N^{6/5}, ...$ 에 점근하게 하는 증가 시퀀스들이 고안되어 있기는 하다. 하지만 일반적인 N 값에 대해 증가율의 차이가 구별하기 어려울 정도로 작기(N에 대한 상수 비율) 때문에 학문적으로만 의미가 있다.⁶
알고리즘 [개정4판]. 2장. 260쪽. ↩

로버트 세지윅의 조언

경험 많은 프로그래머라면 셸-정렬을 선택하는 경우들이 종종 있다. 왜냐하면 셸-정렬은 꽤 큰 배열에 대해서도 적절한 성능을 보여주고, 코드 양도 작고 추가적인 메모리도 사용하지 않기 때문이다. 다음 절들을 통해 좀 더 효율적인 방법들을 알아볼 것이다. 하지만 더 복잡하고, 매우 큰 N을 제외하고는 두 배 정도의 성능 향상밖에는 기대할 수 없다. 만약 정렬 문제에 대한 해결책이 필요하고, 시스템 차원에서의 정렬 기능이 제공되지 않는 환경이라면(예를 들어 하드웨어나 임베디드 시스템 같은) 셸-정렬을 선택하는 것이 안전하다. 더 정교하고 복잡한 방법은 나중에 그것이 정말 필요하다고 판명되었을 때 도입하는 것이 좋다.⁷
알고리즘 [개정4판]. 2장. 261쪽. ↩

함께 읽기

삽입 정렬 (Insertion Sort)

참고문헌

The art of computer programming 3 정렬과 검색(개정2판) / 도널드 커누스 저 / 한빛미디어 / 초판 2쇄 2013년 02월 10일
알고리즘 [개정4판] / 로버트 세지윅, 케빈 웨인 저/권오인 역 / 길벗 / 초판발행 2018년 12월 26일

주석

TAOCP 3권. 5.2장. 112쪽. ↩ ↩²
알고리즘 [개정4판]. 2장. 257쪽. ↩
TAOCP 3권. 5.2장. 113쪽. ↩
TAOCP 3권. 5.2장. 114쪽. ↩
TAOCP 3권. 5.2장. 124쪽. ↩
알고리즘 [개정4판]. 2장. 260쪽. ↩
알고리즘 [개정4판]. 2장. 261쪽. ↩