[알고리즘][파이썬/Python] 쉘 정렬 (Shell Sort)

정의

- 일정 간격(interval) 떨어져 있는 원소들끼리 부분집합을 구성한 후 각 부분집합의 원소들에 대해서 삽입 정렬을 수행하되, 간격을 줄여가며 삽입 정렬을 반복하여 전체 원소들을 정렬하는 방식의 정렬 알고리즘

 

* 쉘 정렬은 삽입 정렬의 문제점을 극복하기 위해 개선한 정렬 알고리즘이다. 삽입 정렬의 경우, 주어진 자료의 정렬 상태에 따라 시간 복잡도가 많이 달라졌는데, 역순으로 정렬되어 있는 형태에 가까울수록 비교횟수가 아주 많이 늘어나는 치명적인 문제점이 존재했다. 그래서 Donald L. Shell 은 '간격(interval)'이라는 개념을 도입하여 위 언급한 문제점을 극복해내는 '쉘 정렬'을 고안해냈다.

 

동작 방식

0. 간격(interval) h = 정렬할 배열(혹은 리스트)의 길이 % 2

1. 첫 번째 원소와 첫번째 원소로부터 h의 배수만큼 간격이 있는 원소들을 부분집합에 포함

2. 부분집합에 포함된 원소에 한해 삽입 정렬을 수행

3. 두 번째 원소와 두 번째 원소로부터 h의 배수만큼 간격이 있는 원소들을 부분집합에 포함

4. 부분집합에 포함된 원소에 한해 삽입 정렬을 수행

5. 위 과정을 h 번째 원소까지 반복

6. 간격(interval) h = h // 2 로 바꿔준 후

7. h가 0 이상일 때까지 1번부터 6번 과정을 반복

 

메모리 사용 공간

n개의 원소에 대하여 n개의 메모리와 매개변수 h에 대한 저장공간 사용

 

연산 시간

- 연산 시간의 대부분을 차지하는 비교횟수는 원소의 상태와 상관없이 간격(interval)을 의미하는 h에 의해 결정됨

- 대부분의 자료에서 쉘 정렬의 시간 복잡도를 계산하는 것은 상당히 힘들다고 설명되어 있으며, 대부분 다수의 실험을 통해 시간 복잡도를 확인했다고 설명되어 있다.

 

- 최선의 경우 시간 복잡도 T(n) = O(N)

- 평균의 경우 시간 복잡도 T(n) = O(N^1.25) ~ O(N^1.5)

- 최악의 경우 시간 복잡도 T(n) = O(N^2)

 

∴ 시간 복잡도 : O(N^2)

* 보수적으로 표현해야 하는 Big-O Notation에 따라 시간 복잡도는 이러하지만, 확실히 삽입 정렬보다는 우수한 성능을 가지고 있다. 원소가 최종적으로 도달해야 하는 위치로 가는 이동 속도가 삽입 정렬에 비해 쉘 정렬이 더욱 빠르기 때문이다.

 

소스 코드

# 쉘 정렬 (Shell Sort)



# 쉘 정렬 - 오름차순 (Shell Sort - Ascending)
def insertionSort_ASC(arr, first, last, h):
    i = first + h
    while i <= last:
        val = arr[i]
        pos = i
        while pos > first and arr[pos-h] > val:
                arr[pos] = arr[pos-h]
                pos -= h
        arr[pos] = val
        i += h
        
def shellSort_ASC(arr):
    n = len(arr)
    h = n//2
    while h > 0:
        for i in range(0, h):
            insertionSort_ASC(arr, i, n-1, h)
        h //= 2
    return arr
    
    
    
# 쉘 정렬 - 내림차순 (Shell Sort - Descending)
def insertionSort_DESC(arr, first, last, h):
    i = first + h
    while i <= last:
        val = arr[i]
        pos = i
        while pos > first and arr[pos-h] < val:
                arr[pos] = arr[pos-h]
                pos -= h
        arr[pos] = val
        i += h

def shellSort_DESC(arr):
    n = len(arr)
    h = n//2
    while h > 0:
		for i in range(0, h):
			insertionSort_DESC(arr, i, n-1, h)
        h //= 2
    return arr
    
    
    
# 난수를 생성하여 test해보기 (Test by random number)
from random import randint

lst = [randint(1, 101) for i in range(8)]
print('Shell Sort(ASC) :', lst, end=' '); print('->', shellSort_ASC(lst))
# Shell Sort(ASC) : [48, 62, 30, 20, 15, 95, 66, 79] -> [15, 20, 30, 48, 62, 66, 79, 95]

lst = [randint(1, 101) for i in range(8)]
print('Shell Sort(DESC) :', lst, end=' '); print('->', shellSort_DESC(lst))
# Shell Sort(DESC) : [67, 93, 18, 44, 4, 78, 74, 82] -> [93, 82, 78, 74, 67, 44, 18, 4]

 

코드를 통해 알고리즘 흐름 알아보기

삽입 정렬때와 마찬가지로 그림을 그릴 만큼의 시간이 허락되지 않아 코드로 쉘 정렬의 흐름을 나타내고자 시도해봤다. 아래 코드로 알고리즘의 흐름을 이해하는 데에 많은 도움이 되었으면 한다.

 

def insertionSort_ASC(arr, first, last, h):
    i = first + h
    while i <= last:
        val = arr[i]
        pos = i
        while pos > first and arr[pos-h] > val:
                arr[pos] = arr[pos-h]
                pos -= h
        arr[pos] = val
        i += h

def shellSort_ASC(arr):
    n = len(arr)
    h = n//2
    while h > 0:
        print('\n------------- 간격(interval) =', h, '------------------')
        for i in range(0, h):
            print('\n정렬 전 :', arr)
            print('부분 집합에 포함된 원소 :', [e for idx, e in enumerate(arr) if idx % h == i])
            insertionSort_ASC(arr, i, n-1, h)
            print('정렬 후 :', arr)
        h //= 2
    print('\n정렬 종료')

from random import randint
# lst = [1,2,3,4,5,6,7,8]
lst = [randint(1, 101) for i in range(8)]
shellSort_ASC(lst)



# ------------- 간격(interval) = 4 ------------------

# 정렬 전 : [97, 90, 20, 33, 26, 63, 78, 84]
# 부분 집합에 포함된 원소 : [97, 26]
# 정렬 후 : [26, 90, 20, 33, 97, 63, 78, 84]

# 정렬 전 : [26, 90, 20, 33, 97, 63, 78, 84]
# 부분 집합에 포함된 원소 : [90, 63]
# 정렬 후 : [26, 63, 20, 33, 97, 90, 78, 84]

# 정렬 전 : [26, 63, 20, 33, 97, 90, 78, 84]
# 부분 집합에 포함된 원소 : [20, 78]
# 정렬 후 : [26, 63, 20, 33, 97, 90, 78, 84]

# 정렬 전 : [26, 63, 20, 33, 97, 90, 78, 84]
# 부분 집합에 포함된 원소 : [33, 84]
# 정렬 후 : [26, 63, 20, 33, 97, 90, 78, 84]

# ------------- 간격(interval) = 2 ------------------

# 정렬 전 : [26, 63, 20, 33, 97, 90, 78, 84]
# 부분 집합에 포함된 원소 : [26, 20, 97, 78]
# 정렬 후 : [20, 63, 26, 33, 78, 90, 97, 84]

# 정렬 전 : [20, 63, 26, 33, 78, 90, 97, 84]
# 부분 집합에 포함된 원소 : [63, 33, 90, 84]
# 정렬 후 : [20, 33, 26, 63, 78, 84, 97, 90]

# ------------- 간격(interval) = 1 ------------------

# 정렬 전 : [20, 33, 26, 63, 78, 84, 97, 90]
# 부분 집합에 포함된 원소 : [20, 33, 26, 63, 78, 84, 97, 90]
# 정렬 후 : [20, 26, 33, 63, 78, 84, 90, 97]

# 정렬 종료

 

삽입 정렬과의 성능 차이

쉘 정렬이 삽입 정렬을 개선했다고 했는데, 그 개선의 정도가 얼마나 되는지 직접 눈으로 확인하고 싶어서 비교를 해봤다. 우선은 극단적인 상황을 주기보다 평균적인 성능 차이는 어떨지 확인해봤다.

 

실험하고자 하는 리스트는 1부터 10000 사이의 정수가 무작위로 1만 개 구성되어 있으며, 해당 리스트를 삽입 정렬 100번, 쉘 정렬 100번 해봤을 때 걸리는 시간을 계산해봤다.

from random import randint
from timeit import *

# Insertion Sort
def insertionSort(arr):
    n = len(arr)
    for i in range(1, n):
        val = arr[i]
        pos = i
        while pos > 0 and arr[pos-1] > val:
            arr[pos] = arr[pos-1]
            pos -= 1
        arr[pos] = val
    return arr  


# Shell Sort
def insertionSort_forShellSort(arr, first, last, h):
    i = first + h
    while i <= last:
        val = arr[i]
        pos = i
        while pos > first and arr[pos-h] > val:
                arr[pos] = arr[pos-h]
                pos -= h
        arr[pos] = val
        i += h
        
def shellSort(arr):
    n = len(arr)
    h = n//2
    while h > 0:
        for i in range(0, h):
            insertionSort_forShellSort(arr, i, n-1, h)
        h //= 2
    return arr

for i in range(5):
    lst = [randint(1, 10001) for i in range(10000)]
    t1 = Timer("insertionSort(lst)", "from __main__ import insertionSort, lst")
    t2 = Timer("shellSort(lst)", "from __main__ import shellSort, lst")
    t1_performance = t1.timeit(number = 100)
    t2_performance = t2.timeit(number = 100)
    a = max(t1_performance, t2_performance)
    b = min(t1_performance, t2_performance)
    print("Insertion Sort * 100 times :", '%.5f' % t1_performance, "seconds")
    print("Shell Sort * 100 times :", '%.5f' % t2_performance, "seconds")
    print("The two Algorithms differ by", "%d" % (a/b), "times in performance.\n")



# Insertion Sort * 100 times : 8.38235 seconds
# Shell Sort * 100 times : 3.83180 seconds
# The two Algorithms differ by 2 times in performance.

# Insertion Sort * 100 times : 6.53540 seconds
# Shell Sort * 100 times : 3.42540 seconds
# The two Algorithms differ by 1 times in performance.

# Insertion Sort * 100 times : 7.04683 seconds
# Shell Sort * 100 times : 2.98648 seconds
# The two Algorithms differ by 2 times in performance.

# Insertion Sort * 100 times : 6.48916 seconds
# Shell Sort * 100 times : 3.80959 seconds
# The two Algorithms differ by 1 times in performance.

# Insertion Sort * 100 times : 6.69183 seconds
# Shell Sort * 100 times : 3.61636 seconds
# The two Algorithms differ by 1 times in performance.

다 만들어놓은 밥상에 숟가락만 얻는 내가 할 말은 아니지만, 이걸 엄청난 개선으로 봐야 될지는 잘 모르겠다. 그렇다면 삽입 정렬을 할 때 최악의 경우인 역순으로 정렬해놓은 상태에서 비교를 해보면 어떨까?

from random import randint
from timeit import *

# Insertion Sort
def insertionSort(arr):
    n = len(arr)
    for i in range(1, n):
        val = arr[i]
        pos = i
        while pos > 0 and arr[pos-1] > val:
            arr[pos] = arr[pos-1]
            pos -= 1
        arr[pos] = val
    return arr  


# Shell Sort
def insertionSort_forShellSort(arr, first, last, h):
    i = first + h
    while i <= last:
        val = arr[i]
        pos = i
        while pos > first and arr[pos-h] > val:
                arr[pos] = arr[pos-h]
                pos -= h
        arr[pos] = val
        i += h
        
def shellSort(arr):
    n = len(arr)
    h = n//2
    while h > 0:
        for i in range(0, h):
            insertionSort_forShellSort(arr, i, n-1, h)
        h //= 2
    return arr

for i in range(5):
    lst = [randint(1, 10001) for i in range(10000)]
    lst.sort(reverse = True)
    t1 = Timer("insertionSort(lst)", "from __main__ import insertionSort, lst")
    t2 = Timer("shellSort(lst)", "from __main__ import shellSort, lst")
    t1_performance = t1.timeit(number = 100)
    t2_performance = t2.timeit(number = 100)
    a = max(t1_performance, t2_performance)
    b = min(t1_performance, t2_performance)
    print("Insertion Sort * 100 times :", '%.5f' % t1_performance, "seconds")
    print("Shell Sort * 100 times :", '%.5f' % t2_performance, "seconds")
    print("The two Algorithms differ by", "%d" % (a/b), "times in performance.\n")
    
# Insertion Sort * 100 times : 13.88854 seconds
# Shell Sort * 100 times : 4.75824 seconds
# The two Algorithms differ by 2 times in performance.

# Insertion Sort * 100 times : 17.87519 seconds
# Shell Sort * 100 times : 3.85622 seconds
# The two Algorithms differ by 4 times in performance.

# Insertion Sort * 100 times : 14.45348 seconds
# Shell Sort * 100 times : 3.34180 seconds
# The two Algorithms differ by 4 times in performance.

# Insertion Sort * 100 times : 13.26045 seconds
# Shell Sort * 100 times : 3.83160 seconds
# The two Algorithms differ by 3 times in performance.

# Insertion Sort * 100 times : 13.22242 seconds
# Shell Sort * 100 times : 3.12352 seconds
# The two Algorithms differ by 4 times in performance.

 확실히 평균적인 상태에서 비교할 때보다는 더욱 명확한 성능 차이를 보여준다. 정말 이런 알고리즘을 개발하는 분들의 비상한 두뇌는 어떻게 되어 있을까? 1%만 닮아보고 싶다.