개요

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

그런 방법 하나가 셸(Donald L. Shell)에 의해서 1959년에 제안되었는데, 제안자의 이름을 따서 셸 정렬(shellsort)이라고 부르게 되었다.1

  • 셸 정렬은 삽입 정렬에 기반을 둔 빠른 정렬이다.2
  • 셸 정렬을 '점감하는 증분 정렬(diminishing increment sort)'라고 부르기도 한다.1

정렬 방식

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

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

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

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

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

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

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

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

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

^      |   |   |   |   |908|   |   |   |   |   |   |   |612|   |   |   |   |   | 908 <-> 612
8 sort |   |   |   |   |   |   |   |   |653|   |   |   |908|   |   |   |   |   |
4 sort |   |   |   |   |   |   |   |   |   |   |   |   |   |   |908|   |897|   | 908 <-> 897
2 sort |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |908|703| 908 <-> 703
1 sort |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |908|

분석

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

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

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

증분 수열 설정에 따라 \(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})\)임을 증명했다.5

세지윅의 책도 읽어보자.

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

로버트 세지윅의 조언

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

함께 읽기

  • [[/insertion-sort]]

참고문헌

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

주석

  1. TAOCP 3권. 5.2장. 112쪽. ↩ ↩2

  2. 알고리즘 [개정4판]. 2장. 257쪽. ↩

  3. TAOCP 3권. 5.2장. 113쪽. ↩

  4. TAOCP 3권. 5.2장. 114쪽. ↩

  5. TAOCP 3권. 5.2장. 124쪽. ↩

  6. 알고리즘 [개정4판]. 2장. 260쪽. ↩

  7. 알고리즘 [개정4판]. 2장. 261쪽. ↩