쉘 정렬.

정렬 방법론.

1. h값에 따라 리스트를 새로 만든다. 리스트의 길이는 15이고 h=4일경우 ex) [1번째,5번째,9번째,13번째],[2번째,6번째,10번째,14번째] .. h=13일 경우는 [1번째,14번째],[2번째,15번째] 두개의 리스트가 나온다.(리스트 길이 15인 경우.)

2. h값은 3*h+1로 정한다. h=1,4,13,40,121,264...이런 순으로 만들어지는데 리스트의 길이보다 작으면서 가장 큰 값을 선택한다. 리스트의 길이가 15면 h=13을 고른다.

3. 정렬시 h=13으로 정렬했으면 그다음으로 작은 h=4로 정렬한다.(그다음은 h=1)

4. 각각 새로 만들어진 작은 리스트들은 각각 삽입 정렬을 수행시킨다.

5. h=1일경우 그냥 삽입 정렬을 수행한다.

특징.

1. 정렬이 된 경우가 유리한 삽입정렬의 특징을 이용해서 성능을 개선시켰다.

2. h=3*h+1로 하는 이유는 이게 효율적이라고 한다...

좋은 그림이 없어서 책의 예제를 빌려옴.

리스트 = [3, 1, 12, 4, 10, 13, 15, 5, 2, 7, 9, 6, 8, 11, 14]가 있다고 할 경우

h=4리스트는 

[3,10,2,8],[1,13,7,11],[12,15,9,14],[4,5,6] 이 만들어진다.

이 각각을 삽입정렬하면 [2,3,8,10],[1,7,11,13],[9,12,14,15],[4,5,6] 이 되는데 

다시 리스트를 만들면

[2,1,9,4,3,7,12,5,8,11,14,6,10,13,15] 가 된다.

h=4를 예로들었는데 이전에 리스트의 길이가 15므로 h=13에 대해서 정렬을 먼저 해야 한다.

시간 복잡도는 O(n^1.25) 이다.(앞에 것들과 비교해서 빠른 편)

# -*- encoding: cp949 -*-
import time
import random
 
N = 10000
def swap(a,i,j):
    a[i],a[j] = a[j],a[i]
 
def CheckSort(a,n):
    Sorted = True
    for i in range(n):
        if a[i] > a[i+1]:
            Sorted = False
        if not Sorted:
            break
    if Sorted: print '정렬 완료.'
    else: print '정렬 오류 발생.'
 
def ShellSort(a,n):
    h = 1
    while h<n:
        h = 3*h+1
    while h>0:
        for i in range(h+1,n+1):
            v = a[i]
            j = i
            while j>h and a[j-h] > v:
                a[j] = a[j-h]
                j -= h
            a[j] = v
        h /= 3

def main():
    a = [random.randint(1,65536) for i in range(0,N+1)] #랜덤한 10000개의 데이터
    a[0] = -1
    start_time = time.time()
    ShellSort(a,N)
    print '(랜덤)쉘 정렬의 실행 시간 (N = {} ) : {}'.format(N,time.time()-start_time)
    CheckSort(a,N)

    a = [i for i in range(0,N+1)] #정렬된 10000개의 데이터
    a[0] = -1
    start_time = time.time()
    ShellSort(a,N)
    print '(최고)쉘 정렬의 실행 시간 (N = {} ) : {}'.format(N,time.time()-start_time)
    CheckSort(a,N)
 
    a = [i for i in range(N,-1,-1)] #최악의 경우의 10000개의 데이터
    a[0] = -1
    start_time = time.time()
    ShellSort(a,N)
    print '(최악)쉘 정렬의 실행 시간 (N = {} ) : {}'.format(N,time.time()-start_time)
    CheckSort(a,N)
 
if __name__=='__main__':
    main()