[알고리즘] 쉘 정렬 알고리즘

쉘 정렬 알고리즘은 삽입정렬을 간단하게 변형한 것입니다.

원소의 비교 연산과 먼 거리로의 원소 이동을 줄이려는 목적을 가진 알고리즘입니다.

인덱스 간격은 쉽게 계산 가능해야하고, 홀수와 짝수가 번갈아 나오면서 순차되는 것이 좋습니다.

 

ADL

shellSort(a[], n)
	for(h <- 1; 3*h+1 < 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()

쉘 정렬 알고리즘 여러개의 서브리스트로 분할하는 것에서 시작하여, 마지막 단계에서는 배열 전체에 대해 삽입 정렬을 적용 시킨다.

최선의 경우 성능은 O(NlogN)이고, 평균적인 경우는 O(N^4/3), 최악의 경우는 O(N^3/2)으로 알려져있다.

 

제자리 정렬

 

멀리있는 원소끼리 교환하기에 안정적인 알고리즘은 아님

 

PYTHON

def shellShort(a,n):
	h=1
    while 3*h+1 < n:
    	h = 3*h+1
    while h > 0 :
    	h = h/3
    	for i in range(h+1, n+1):
			v, j = a[i], i
            while j > h and a[j-h] > v:
            	a[j]=a[j-h]
                j -= h
            a[h] = v
        h=int(h/3)

*** 쉘정렬 더 이해 필요***