셸 정렬은 삽입 정렬을 기반으로 한다. 원래 리스트를 작은 서브 리스트로 나눈 후, 각각을 삽입 정렬로 정렬하여 성능을 개선하는 일반적인 방법이다.
Sapientia University에서 만든 유용한 동영상은 이 과정을 헝가리 민속 춤으로 보여준다.
삽입 정렬이 인접한 요소들을 비교해 순서가 맞지 않으면 서로 바꾸는 방식과 달리, 셸 정렬 알고리즘은 서로 멀리 떨어진 요소들을 비교한다.
요소들 사이의 거리를 *간격(gap)*이라고 한다. 비교 대상 요소들의 순서가 맞지 않으면 간격을 건너뛰어 서로 바꾼다. 이렇게 하면 삽입 정렬에서 흔히 발생하는 중간 단계의 복사 작업을 많이 줄일 수 있다.
큰 간격으로 요소들을 이동하면 배열이 부분적으로 정렬되는 속도가 빨라진다. 이렇게 되면 후반부 단계에서 많은 요소를 바꿀 필요가 없어져 정렬 속도가 더 빨라진다.
한 단계가 완료되면 간격을 더 작게 만들고 새로운 단계를 시작한다. 이 과정은 간격이 1이 될 때까지 반복된다. 간격이 1이 되면 알고리즘은 삽입 정렬과 동일하게 동작한다. 하지만 이 시점에서는 데이터가 이미 상당히 잘 정렬된 상태이므로 마지막 단계가 매우 빠르게 진행된다.
배열 [64, 20, 50, 33, 72, 10, 23, -1, 4]를 쉘 정렬로 정렬한다고 가정해 보자.
먼저 배열의 길이를 2로 나눈다:
n = floor(9/2) = 4
이 값이 간격(gap) 크기가 된다.
n개의 서브리스트를 만든다. 각 서브리스트는 n 간격으로 떨어진 항목들로 구성된다. 이 예제에서는 네 개의 서브리스트를 만든다. 각 서브리스트는 insertionSort() 함수로 정렬된다.
이해가 잘 되지 않을 수 있으므로, 실제로 어떤 일이 일어나는지 자세히 살펴보자.
첫 번째 패스는 다음과 같다. n = 4이므로 네 개의 서브리스트를 만든다:
sublist 0: [ 64, xx, xx, xx, 72, xx, xx, xx, 4 ]
sublist 1: [ xx, 20, xx, xx, xx, 10, xx, xx, xx ]
sublist 2: [ xx, xx, 50, xx, xx, xx, 23, xx, xx ]
sublist 3: [ xx, xx, xx, 33, xx, xx, xx, -1, xx ]
각 서브리스트는 원본 배열에서 4번째 항목만 포함한다. 서브리스트에 포함되지 않은 항목은 xx로 표시한다. 첫 번째 서브리스트는 [ 64, 72, 4 ]이고, 두 번째는 [ 20, 10 ]이다. 이렇게 "간격"을 사용하는 이유는 새로운 배열을 만들지 않고 원본 배열 내에서 서브리스트를 구성하기 위함이다.
이제 각 서브리스트에 대해 insertionSort()를 한 번씩 호출한다.
이 버전의 삽입 정렬은 뒤에서 앞으로 정렬한다. 서브리스트의 각 항목은 다른 항목들과 비교된다. 순서가 잘못된 경우 값을 교환하고, 서브리스트의 시작 부분에 도달할 때까지 계속 이동한다.
서브리스트 0의 경우, 4와 72를 교환한 다음 4와 64를 교환한다. 정렬 후 이 서브리스트는 다음과 같이 된다:
sublist 0: [ 4, xx, xx, xx, 64, xx, xx, xx, 72 ]
다른 세 개의 서브리스트도 정렬 후 다음과 같이 된다:
sublist 1: [ xx, 10, xx, xx, xx, 20, xx, xx, xx ]
sublist 2: [ xx, xx, 23, xx, xx, xx, 50, xx, xx ]
sublist 3: [ xx, xx, xx, -1, xx, xx, xx, 33, xx ]
전체 배열은 이제 다음과 같이 된다:
[ 4, 10, 23, -1, 64, 20, 50, 33, 72 ]
아직 완전히 정렬되지는 않았지만 이전보다 더 정렬된 상태이다. 이로써 첫 번째 패스가 완료된다.
두 번째 패스에서는 간격 크기를 2로 나눈다:
n = floor(4/2) = 2
이제 두 개의 서브리스트를 만든다:
sublist 0: [ 4, xx, 23, xx, 64, xx, 50, xx, 72 ]
sublist 1: [ xx, 10, xx, -1, xx, 20, xx, 33, xx ]
각 서브리스트는 2번째 항목만 포함한다. 다시 insertionSort()를 호출해 이 서브리스트를 정렬한다. 결과는 다음과 같다:
sublist 0: [ 4, xx, 23, xx, 50, xx, 64, xx, 72 ]
sublist 1: [ xx, -1, xx, 10, xx, 20, xx, 33, xx ]
각 리스트에서 두 개의 요소만 순서가 잘못된 것을 알 수 있다. 따라서 삽입 정렬이 매우 빠르게 수행된다. 이는 첫 번째 패스에서 이미 배열을 어느 정도 정렬했기 때문이다.
전체 배열은 이제 다음과 같이 된다:
[ 4, -1, 23, 10, 50, 20, 64, 33, 72 ]
이로써 두 번째 패스가 완료된다. 마지막 패스의 간격 크기는 다음과 같다:
n = floor(2/2) = 1
간격 크기가 1이면 단 하나의 서브리스트, 즉 배열 자체가 된다. 다시 insertionSort()를 호출해 이를 정렬한다. 최종 정렬된 배열은 다음과 같다:
[ -1, 4, 10, 20, 23, 33, 50, 64, 72 ]
쉘 정렬의 성능은 대부분의 경우 **O(n^2)**이고, 운이 좋다면 **O(n log n)**이다. 이 알고리즘은 불안정 정렬을 생성하며, 동일한 값을 가진 요소들의 상대적 순서를 변경할 수 있다.
"갭 시퀀스"는 초기 갭의 크기와 각 반복마다 갭을 어떻게 줄여나갈지 결정한다. 셸 정렬이 효율적으로 동작하려면 적절한 갭 시퀀스가 중요하다.
이 구현에서 사용한 갭 시퀀스는 셸의 원래 버전에서 나온 것이다. 초기값은 배열 크기의 절반으로 설정하고, 이후 각 단계마다 2로 나눈다. 갭 시퀀스를 계산하는 다른 방법들도 존재한다.
이 코드는 Matthijs가 오래전에 사용했던 Commodore 64 BASIC 버전의 셸 정렬 알고리즘이다. 그는 이 코드를 거의 모든 프로그래밍 언어로 포팅했다:
61200 REM S는 정렬할 배열
61205 REM AS는 배열 S의 요소 개수
61210 W1=AS
61220 IF W1<=0 THEN 61310
61230 W1=INT(W1/2): W2=AS-W1
61240 V=0
61250 FOR N1=0 TO W2-1
61260 W3=N1+W1
61270 IF S(N1)>S(W3) THEN SH=S(N1): S(N1)=S(W3): S(W3)=SH: V=1
61280 NEXT N1
61290 IF V>0 THEN 61240
61300 GOTO 61220
61310 RETURNSwift로 구현한 셸 정렬(Shell Sort) 예제는 다음과 같다:
var arr = [64, 20, 50, 33, 72, 10, 23, -1, 4, 5]
public func shellSort(_ list: inout [Int]) {
var sublistCount = list.count / 2
while sublistCount > 0 {
for pos in 0..<sublistCount {
insertionSort(&list, start: pos, gap: sublistCount)
}
sublistCount = sublistCount / 2
}
}
shellSort(&arr)Swift 알고리즘 클럽을 위해 Mike Taghavi와 Matthijs Hollemans가 작성함