[Algorithm] Shell Sort(쉘 정렬)

Code

def shell_sort(a):
    n=len(a)
    gap=n//2
    while(gap>=1):
        if(gap%2==0): gap+=1
        for i in range(gap,n):
            j=i
            while(j>=gap and a[j-gap]>a[j]):
                a[j-gap], a[j] = a[j], a[j-gap]
                j-=gap
        print('  Gap=', gap, a)
        gap=gap//2

a = [10, 4, 5, 1, 8, 6, 2, 7, 9, 3]

print(a)
shell_sort(a)
print(a)

 

정리

삽입정렬에 전처리 과정을 추가한 알고리즘

gap을 사용해 정렬된 간격을 줄인다.

 

시간복잡도

최악의 경우 O(n^2)

평균의 경우 O(n^1.5) - Hibbard의 간격

 

특징

간격을 어떻게 설정하냐에 따라 수행시간이 달라진다.

일반적으로 입력이 크지 않은 경우에 매우 좋은 성능을 보인다.