셸 정렬
셸 정렬은 단순 삽입 정렬에서 특정 원소를 삽입할 위치가 멀리 떨어져 있으면 이동 횟수가 많아지는 단점을 보완한 정렬 알고리즘입니다. 비교하는 횟수를 확 줄인 알고리즘이죠.
배열 [8, 1, 4, 2, 7, 6, 3, 5]를 셸 정렬로 정렬하는 예시입니다. 먼저 서로 4칸씩 떨어진 원소를 꺼내어 (8, 7), (1, 6), (4, 3), (2, 5)의 4개의 그룹으로 나눈 후 각자 따로 정렬합니다. 그럼 다음과 같이 [7, 1, 3, 2, 8, 6, 4, 5]가 됩니다.(4-정렬)
다음은 2칸 떨어진 원소를 모두 꺼내 (7, 3, 8, 4), (1, 2, 6, 5) 두 그룹으로 나누고, 각각 정렬을 수행합니다.(2-정렬)
마지막으로 1칸 떨어진 배열, 즉 배열 전체에 단순 삽입 정렬을 적용하면 정렬이 완료됩니다.(1-정렬)
즉, 셸 정렬은 조금이라도 정렬이 된 상태에 가까운 배열로 만든 다음 마지막 삽입정렬을 하여 이동 횟수를 줄인 조금 더 효율적인 정렬을 하는 알고리즘입니다.
그럼 초기에 h-정렬을 하는 h 값을 어떻게 선택할까요? 일반적으로 h 값은 배열의 원소 수인 n을 9로 나누었을 때 그 몫을 넘지 않도록 설정해야 합니다. 또한 다음 수열을 사용했을 때 간단하고 효율적으로 정렬을 할 수 있습니다.
h = 1
while h < n//9:
h = h * 3 + 1
다음은 셸 정렬 알고리즘 코드입니다.
def shell_sort(a: MutableSequence) -> None:
n = len(a)
h = 1
while h < n // 9:
h = h * 3 + 1
while h > 0:
for i in range(h, n):
j = i - h
tmp = a[i]
while j >= 0 and a[j] > tmp:
a[j + h] = a[j]
j -= h
a[j + h] = tmp
h //= 3
셸 정렬의 시간 복잡도는 O(n^1.25)이고 단순 정렬의 시간 복잡도인 O(n^2)보다 매우 빠릅니다. 하지만 셸 정렬은 이웃하지 않고 떨어져 있는 원소를 서로 교환하므로 안정적이지 않습니다.
출처
Do it! 자료구조와 함께 배우는 알고리즘 입문 : 파이썬 편
