쉘 정렬 (Shell Sort)

1. Introduction

쉘 정렬은 삽입 정렬이 어느정도 정렬된 리스트에서 좋은 효율을 보인다는 점에서 착안한 삽입정렬의 variation이다. gap에 따라, 떨어진 원소들을 먼저 정렬하고 gap을 줄여나가면서 정렬을 완성하는 정렬 알고리즘이다. 

2. Approach

다음 이미지는 쉘 정렬의 과정을 보여준다. 출처는 위키피디아.

Animation of Shell Sort

다음 코드는 파이썬으로 구현한 쉘 정렬이다.

def shell(arr, a, b): 
  
    n = b-a
    gap = n//3 + 1
  
    while gap > 0: 
  
        for i in range(a+gap,b+1): 
            temp = arr[i] 
            j = i 
            while  j >= gap and arr[j-gap] >temp: 
                arr[j] = arr[j-gap] 
                j -= gap 
            arr[j] = temp
        if gap == 1:
            gap = 0
        else:
            gap = gap//3 + 1

3. Discussion

쉘 정렬은 in-place한 알고리즘에 속하나, 기반 알고리즘인 삽입 정렬과는 달리 stable하지 않은 알고리즘에 속한다.

쉘 정렬은 gap sequence에 따라 성능이 변하는 걸로 알려져있는데, 단순히 gap을 전체의 반으로 나눠가는 경우 성능이 $O(n^2)$으로 원래의 삽입 정렬에 비해 크게 성능이 변하지 않는다고 한다.

gap이 ${N\over 3} +1$으로 표현되면, 시간복잡도는 $O(n^{3\over 2} )$으로 나타난다.

gap sequence가 prefix로 1이 포함된 $4^k + 3*2^{k-1}+1$ 즉, $1, 8, 23, 77, 281, ...$로 표현되면, 시간복잡도는 $O(n^{4\over 3} )$으로 나타난다.

실험적으로 가장 이상적인 gap sequence는 $1, 4, 10, 23, 57, 132, 301, 701, 1750$이고 이 다음부터는 2.25배에 내림(round down)으로 얻어진다고 한다.