셸 정렬 (Shell Sort)
셸 정렬은 정렬 방법의 원리로만 보자면 “분할 증분 정렬”(diminishing incremental sort)이라고도 불리는 방법이며, 굉장히 오래된 정렬 알고리듬 중 하나이다. 이 정렬 방법은 삽입 정렬을 근간으로 하면서 삽입 정렬의 성능을 간단한 아이디어로부터 크게 증가시키는 방법이다.
삽입 정렬은 왼쪽에 있는 원소부터, 그 원소가 이동할 수 있는 ‘가장 왼쪽 자리’에 그 값을 삽입하여 정렬해 나가는 방식이다. 이 때 ‘삽입’을 위한 공간을 만들기 위해 원래자리부터 삽입될 자리 사이의 값들이 하나씩 오른쪽으로 이동해야 한다. 따라서 삽입 정렬은 어떤 원소가 이동해야 할 거리가 크면 클수록 효율이 떨어지며 배열이 반대로 정렬되어 있는 경우가 이에 해당할 것이다.
만약 먼거리를 이동할 때 한 번에 N칸 씩 비교하고 이동한다면 전체 이동 횟수는 1/N만큼 줄어들 수 있을 것이다. 셸 정렬은 이 원리를 이용한다. 개괄적인 방식은 다음과 같다.
- 한 번에 이동할 칸 수 N을 정한다. 여기서는 일단 임의로 4라고 하자.
- 한 번에 이동하는 칸 수는 정렬의 간격이 된다. 즉 12번 위치의 값은 8번, 4번, 0번 위치의 값과 비교하여 이동하고, 이 때 값들은 0 > 4, 4 > 8, 8 > 12, 12 > 0 로 이동하게 된다.
- 0, 4, 8, 12, .. 의 원소들을 대략적으로 정렬했으면, 1, 5, 9, 13, … 의 원소들도 같은 식으로 정렬한다.
- 마찬가지의 방법으로 2와 3으로 시작하는 간격 4의 원소들도 정렬한다.
전체 길이가 배열의 길이가 L일 때, L/4인 배열 4개를 삽입정렬했다. 이 상태에서 간격을 다시 2로 줄여서 0, 1을 시작점으로 하는 부분 배열을 다시 삽입정렬한다. 이 때, 이 배열들은 앞단계에서 부분적으로 보다 더 정렬된 상태에 가깝기에 (작은 값들이 평균적으로 왼쪽으로 더 이동했으므로) 좀 더 적은 교환으로 완료할 수 있을 것이다. 그리고 더 촘촘한 간격에 의해 더 많은 작은 값들이 평균적으로 왼쪽에 와 있다고 볼 수 있다. 간격을 더 줄여서 1이 되면 일반 삽입정렬과 동일하다. 최종적으로 삽입정렬로 배열 전체를 정렬한다.
삽입 정렬을 여러번 수행하는 것이 실제 전체 배열에 대해 한 번 정렬하는 것보다 빨라진다는 것이 직관적으로는 와 닿지 않지만, 삽입정렬의 최악의 시간복잡도는 
구현
일반적인 삽입 정렬과 달리 이동거리(gap) 만큼씩 움직이면서 부분적인 삽입 정렬을 할 수 있는 헬퍼 함수가 있다면 셸 정렬을 쉽게 구현할 수 있다. 하나의 gap 값에 대해서 0, 1, .. gap-1 을 시작 위치로 하여 부분 정렬을 수행하고, gap을 절반이나 1/3 등으로 줄여가면 되겠다.
먼저 헬퍼 함수로 사용될 gi_sort()를 구현하고 셸 소트에서 이 헬퍼 함수를 호출 하는 식으로 구현하는 것이 이해하기도 쉽고 편리하다. 우선 헬퍼함수는 한 번에 1씩 움직이는 것이 아닌 gap만큼씩 움직이는 삽입 정렬 코드와 거의 동일할 것이며, shell 소트는 gap을 점점 줄여나가면서 매번 range(gap)에 대해서 gi_sort()를 호출하면 된다.
from typing import TypeVar, List
T = TypeVar('T')
def gi_sort(arr: List[T], gap: int=0, start: int=0):
''' gap_interval_sort: start 부터 시작해서 gap씩 건너뛴 값들에 대해서
삽입 정렬을 수행한다. '''
for i in range(start, len(arr), gap):
# c : 현재 위치 인덱스의 커서
# v : 비교하는 기준값
c, v = i, arr[i]
while c > gap and arr[c-gap] > v:
arr[c] = arr[c-gap]
c -= gap
arr[c] = v
def shell_sort(arr: List[T]):
''' 배열의 길이 L의 절반으로 gap을 정하고
gap을 점차 줄여 나간다.'''
gap = len(arr) // 2
while gap > 0:
# 각 gap에 대해서 1~gap 범위를 start로 주고 gi정렬
for start in range(gap):
gap_sort(arr, gap, start)
# gap은 반으로 줄여나간다.
gap //= 2그럼, 삽입 정렬과의 성능을 비교해보면 어떨까? 셸 정렬이 제자리 정렬이다보니, 배열을 복사하는데 드는 시간도 생각해야 겠지만 동일한 배열을 정렬하는 성능의 비교는 충분히 할 수 있을 듯 하다.
%%timeit
xs = ns[:]
insert_sort(xs)
264 ms ± 3.44 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
%%timeit
xs = ns[:]
shell_sort(xs)
15.6 ms ± 317 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
팁
위에서 작성한 코드는 별도의 헬퍼 함수를 사용하여 작성했다. 하지만 실제로는 for 문내에서 동일한 규칙대로 함수를 호출하므로 함수는 하나로 합쳐질 수 있다. 또한 삽입 정렬의 구현에서와 같이 슬라이스를 사용하여 값 이동의 횟수를 더 줄일 수 있을 것이다.
참고로 gap의 길이를 전체 배열의 절반 길이로부터 2로 나눠가는 것 보다는 N / 3 + 1 의 형태로 감소시켜 가는 것이 더 좋은 성능을 보인다고 알려져 있다.
