셸 정렬

정의

 

셸 정렬(shell sort)은 단순 삽입 정렬의 장점을 살리고 단점은 보완하여 더 빠르게 정렬하는 알고리즘이다.

 

단순 삽입의 특징

- 장점 : 이미 정렬을 마쳤거나 정렬이 거의 끝나가는 상태에서는 속도가 아주 빠르다.

- 단점 : 삽입할 위치가 멀리 떨어져 있으면 이동 횟수가 많아진다.

 

셀 정렬은 먼저 정렬할 배열의 원소를 그룹으로 나눠 각 그룹별로 정렬을 수행한다. 그 후 정렬된 그룹을 합치는 작업을 반복하여 원소의 이동 횟수를 줄인다.

 

위의 배열은 먼저 서로 4칸씩 떨어진 원소를 꺼내어 4개의 그룹으로 나누고 그룹별로 정렬한다. 이런 방법을 '4 - 정렬'이라고 한다. 아직 정렬을 마치지 않았지만 정렬의 상태와 가까워졌다. 

 

 

이어서 2칸 떨어진 원소를 모두 꺼내 '2 - 정렬'을 진행한다.

 

 

이후 '1 - 정렬'을 적용하면 오른차순 정렬이 완료된다. 

삽입 정렬에 비해 정렬 횟수는 늘어나지만 전체적으로 원소의 이동 횟수가 줄어들어 효율적이다.

 

<code>

def shell_sort(a):
    n = len(a)
    h = n // 2 # h의 초깃값은 배열의 절반값이다 while문을 반복할 때마다 2배씩 줄어든다.
    while h > 0:
        for i in range(h, n):   # 5~12행은 단순 삽입 정렬을 수행하는 과정이다. 다른점은 주목 원소와 비교 원소가 h개만큼 떨어져 있다는 것.
            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 //= 2
        
if __name__ == '__main__':
    print('셸 정렬을 수행합니다.')
    num = int(input('원소 수를 입력하세요 : '))
    x = [None] * num
    
    for i in range(num):
        x[i] = int(input(f'x[{i}]: '))
        
    shell_sort(x)
    
    print('오름차순으로 정렬했습니다.')
    for i in range(num):
        print(f'x[{i}] = {x[i]}')

 

 

부분 집합으로 나누는 h의 초깃값은 전체 배열의 절반값이다. while 문을 반복할 때마다 다시 2로 나눈 값으로 업데이트한다. 즉, 원소 수가 8이면 4, 2, 1순으로 변화하고, 7이면 3, 1순으로 변한다.

 

셸 정렬의 시간 복잡도는 O(n^1.25)이고 단순 정렬의 시간 복잡도인 O(n^2)보다 매우 빠르다. 그러나 셸 정렬 알고리즘은 이웃하지 않고 떨어져 있는 원소를 서로 교환하므로 안정적이지 않다.