쉘 정렬(Shell Sort)

shell sort는 삽입 정렬의 단점을 보안하기 위해 고안된 알고리즘이다.

삽입 정렬은 처음부터 끝까지 다 검사하지만 이는 처음에 몇개의 서브리스트로 나누어 작업한 다음에 삽입 정렬을 수행하는 것이다.

여기서 일정한 간격 h 를 두고 서브리스트를 구성하게 된다. 보통 h는 h = 3h+1 로 구성한다.

이를 ADL 로 나타내보자

shellsort(a[],n)
	for (h <- 1; h < n; h <- 3*h+1) do {}; // 첫번째 h값 계산
    for (; h>0; h <- h/3) do { // h 감소시켜가면서 진행
    	for (i <- h+1; i <= n; i <- i+1) do {
        	v <- a[i];
            j <- i;
            while (j > h and a[j-h] > v) do {
            	a[j] <- a[j-h];
                j <- j-h;
            }
         	a[j] <- v;
         }
     }
end shellsort()

첫번쨰에서 서브리스트를 나누는 h를 계산한담에 서브리스트를 나눈 후 삽입 정렬을 하게 된다.

삽입 정렬은 https://bigdata-analyst.tistory.com/300 참고하면 된다

이것도 예를 들어서 한 번 보자

input = [3,14,12,4,10,13,15,5,2,7,9,6,8,11,1]

shellsort

삽입 정렬한 과정은 따로 적지 않았다. 서브리스트를 만들어 미리 정렬해놓고 마지막에 삽입 정렬을 수행하는 방식이다.

이 방식은 최선의 경우 성능은 \( O(nlogn) \) 이고 최악의 경우는 \( O(N^{ \frac{4}{3}} ) \)이다.

python code는 다음과 같다

def shellsort(a,n):
    for h in range(1,n):
        h = 3*h+1
    while h > 0 :
        h = h//3
        if h == 0:
            break
        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      
    return a
a = [-1,3,1,14,12,4,10,13,15,5,2,7,9,6,8,11,14]
shellsort(a,len(a)-1)