Shell Sort

퀵, 힙, 병합, 카운팅 정렬 등
일반적으로 $O(n\times \log n)$ 의 시간 복잡도를 가지는 정렬의 존재는 알고 있었으나,
Shell Sort (셸 정렬) 는 처음 알게되어 공부한 것을 정리해보았다.

단순 삽입 정렬의 개선

[ 단순 삽입 정렬 코드 ]

def insertion_sort(target_list):
    for i in range(1, len(target_list)):
        key = target_list[i]
        j = i - 1
        while j >= 0 and key < target_list[j]:
            target_list[j + 1] = target_list[j]
            j -= 1
        target_list[j + 1] = key

단순 삽입 정렬은 정렬이 거의 완료된 데이터에 대한 정렬은 굉장히 빠르지만,
정렬 대상 원소를 삽입 할 위치가 멀수록 이동 횟수 가 많아진다는 한계를 가지고 있다.

이러한 단순 삽입 정렬의 장점을 살리고, 단점의 보완을 위해 만들어진 정렬이
바로 Shell Sort 이다.

Gap

Shell Sort가 단순 삽입 정렬의 단점을 보완하기 위해 사용한 것은 바로 Gap 이다.

먼저, Gap이 무엇인지 알아보자.

🤔 Gap 이란?

단순 삽입 정렬은
1번 index부터 시작하여 현재 index 요소(삽입될 변수의 값)를 별도로 저장하고
삽입될 변수의 값과 index-1 위치의 요소를 비교한다.
삽입될 변수의 값이 더 클때까지 비교 대상 요소의 index를 감소하며 비교를 반복한다.

이 때, 현재 삽입될 변수의 값과 비교할 요소와의 간격 (위에서는 1)이 바로 Gap 이다.

반대로 이야기 하면, Shell Sort의 관점에서
단순 삽입 정렬은 Gap이 1로 고정되어있는 정렬 방식이라고 할 수 있다.

🤷‍ Gap을 어떻게 이용할까?

Shell Sort 는 Gap을 순차적으로 줄여 나가 며
먼저 서로 멀리 떨어져 있는 요소를 정렬하고,
정렬할 요소 사이의 간격을 줄여 나가는 방식으로 정렬한다.

❓ 왜 더 빠를까?

위에서 이야기 한 단순 삽입 정렬의 장/단점 에 의해 가능하다.

• 단점 보완
  먼 간격의 원소를 정렬해 나가는것은 상대적으로 적은 이동을 요하며,

• 장점 유지
  완전히 정렬된 것은 아니나,
  정렬을 거의 마친 상태 에 가까워지게 만들기 때문이다.

🔖 Gap에 관하여

그럼 다시 Gap을 순차적으로 줄여 나가 는 방법에 대해 궁금해 지는데,
Shell Sort에서 사용할 수 있는 Gap 의 최적 시퀀스는
이미 구해져있는 몇가지 종류가 있다.

아래는 Gap Sequence 의 몇가지 예시이다.
Shell Sort의 성능은 사용하는 Gap Sequence 유형에 따라 달라진다.

• Knuth's increment sequence : $(3^{n} - 1)/2$
  [ 0, 1, 4, 13, 40, 121, 364, 1093, 3280, 9841, 29524, 88573, ... ]

• Sedgewick's increments sequence : $4^{n+1} + 3\times 2^n + 1$
  [ 1, 8, 23, 77, 281, 1073, 4193, 16577, 65921, 262913, ... ]

• Papernov & Stasevich increment sequence
  [ 1, 3, 5, 9, 17, 33, 65, ... ]

• Pratt
  [ 1, 2, 3, 4, 6, 9, 8, 12, 18, 27, 16, 24, 36, 54, 81, ... ]

• Hibbard's increments sequence : $2^{n}-1$
  [ 1, 3, 7, 15, 31, 63, 127, 255, 511, … ]

구현

파이썬을 이용해 구현하였다.
Gap Seqeunce 는 위 예시에 있는 Knuth's increment sequence를 구현해서 사용하였으며

더 아래에는 단순 삽입 정렬과의 정렬 속도도 비교해보았다.

Shell Sort 구현

[ 구현 코드 ]

def shell_sort(target_list):
	# `Knuth 시퀀스`에 따라 첫 gap값을 만들어준다.
    gap = 1 
    while gap < len(target_list):  # 단, 리스트 전체 길이보다 짧게
        gap = gap * 3 + 1
        
    # gap을 감소시키며 insertion sort를 반복한다.
    while gap > 0:
    	# 삽입정렬시 parameter로 gap을 전달한다.
        insertion_sort(target_list, gap)
        # gap : ... -> 121 -> 40 -> 13-> 4 -> 1
        gap = gap // 3


def insertion_sort(target_list, gap):
	# 전달받은 gap을 첫 index로 하여 삽입 정렬을 시작한다.
    # gap이 없는 단순 삽입 정렬에서는 아래의 gap 위치에 모두 1이 들어간다.
    for i in range(gap, len(target_list)):
        key = target_list[i]
        j = i - gap
        while j >= 0 and key < target_list[j]:
            target_list[j + gap] = target_list[j]
            j -= gap
        target_list[j + gap] = key

Insertion Sort VS Shell Sort

Python의 random 모듈을 이용하여
범위내의 랜덤값을 가진 배열을 만들어
삽입 정렬과 셸 정렬에 소요되는 시간을 비교해보았다.

배열 길이(개)	삽입 정렬 소요 시간 (초)	셸 정렬 소요 시간 (초)
10000	1.800	0.006
20000	7.162	0.069
30000	16.209	0.095
40000	29.190	0.120

[ 소요시간 비교에 사용한 코드 ]

import time
import random


def shell_sort(target_list):
    gap = 1
    while gap < len(target_list):
        gap = gap * 3 + 1
    while gap > 0:
        insertion_sort(target_list, gap)
        gap = gap // 3


def insertion_sort(target_list, gap):
    for i in range(gap, len(target_list)):
        key = target_list[i]
        j = i - gap
        while j >= 0 and key < target_list[j]:
            target_list[j + gap] = target_list[j]
            j -= gap
        target_list[j + gap] = key


max_num = int(input())

num_list = [i for i in range(max_num)]

start = time.time()  # 시작 시간 저장
random.shuffle(num_list)
print("shuffle time :", time.time() - start)  # 현재시각 - 시작시간 = 실행 시간

start = time.time()  # 시작 시간 저장
shell_sort(num_list)
print("shell sorting time :", time.time() - start)  # 현재시각 - 시작시간 = 실행 시간


print()
num_list = [i for i in range(max_num)]

start = time.time()  # 시작 시간 저장
random.shuffle(num_list)
print("shuffle time :", time.time() - start)  # 현재시각 - 시작시간 = 실행 시간

start = time.time()  # 시작 시간 저장
insertion_sort(num_list, 1)
print("insertion sorting time :", time.time() - start)  # 현재시각 - 시작시간 = 실행 시간

참고
Analysis of Shellsort and Related Algorithms
Algorithm Analysis
Programiz : 'Shell Sort Algorithm'
StackOverflow : 'Fastest gap sequence for shell sort?'