쉘 정렬

개념

• 도널드 L. 셸이 고안한 방법이다.
• 원소를 그룹으로 나누고 정렬한 후 정렬된 배열을 합치는 작업을 반복한다.
• 단순 삽입 정렬의 단점(삽입할 위치가 멀면 이동 횟수가 많아짐)을 보완하기 위한 방법이다.

알고리즘 (파이썬)

a = [8,1,4,2,7,6,3,5]  #입력 배열

n=len(a)    #입력 배열의 길이 (=원소의 개수)

h = n//2    #gap

while h>0:
    for i in range(h,n):    
        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

원소 개수 // 2만큼 간격을 선정하고, 그 간격만큼 배열에서 부분 리스트를 생성한다.
생성된 부분리스트에서 삽입정렬을 수행한다.
한 pass가 끝나면 gap//2하여 gap이 1이 될 때까지 반복한다.
gap=1인 경우는 단순 삽입정렬과 동일하다.

gap 값의 선택

원소들이 서로 충분히 섞일 수 있도록 단순히 n을 2로 나누는 것 보다는 h*3+1의 수열을 사용한다 (knuth의 수열)