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

쉘 정렬 

- 삽입 정렬을 이용하여 배열 뒷부분의 작은 숫자를 앞부분으로 빠르게(작은 숫자들이 마치 '점프하여' 앞으로 이동)이동시키고, 동시에 앞부분의 큰 숫자는 뒷부분으로 이동시키며, 가장 마지막에는 삽입 정렬을 수행

- 버블 정렬과 삽입 정렬의 단점을 보완

 

ex) 30 60 90 10 40 80 40 20 10 60 50 30 40 90 80

 

간격(gap)이 5인 그룹으로 나누어 정렬하면

정렬한 결과 80과 90 같은 큰 숫자는 뒷부분, 20과 30 같은 작은 숫자는 앞부분으로 이동한 것을 확인할 수 있음

>>다음에는 gap을 5보다 작게 하여, 정렬을 수행

단, 마지막에는 반드시 간격을 1로 놓고 수행해야 함(다른 그룹에 속하여 서로 비교되지 않은 숫자가 있을 수도 있기 때문에)

=> 모든 원소를 1개의 그룹으로 여기는 것, 이는 삽입 정렬의 그 자체

 

h=5일 때 정렬 결과 나열: 30 30 20 10 40 50 40 40 10 60 80 60 90 90 80

 

h=3일 때 정렬 결과 나열: 10 30 10 30 40 20 40 40 50 60 80 60 90 90 80 

 

h=1일 때(=삽입 정렬과 동일) 정렬 결과 나열: 10 10 20 30 30 40 40 40 50 60 60 80 80 90 90

 

알고리즘

입력: 크기가 n인 배열 A

출력: 정렬된 배열 A

for each gap h=[h0>h1>...>hk=1]
	for i=h to n-1
    	CurrentElement = A[i]
        j=i
        while(j>=h) and (A[j-h]>CurrentElement)
        	A[j]=A[j-h]
            j=j-h
        A[j]=CurrentElement
return A

 

시간 복잡도

:사용하는 간격에 따라 분석해야 함

 

최악 경우 시간 복잡도: 히바드(Hibbard)의 간격

- 2^k-1(2^k-1, ..., 15, 7, 5, 3, 1)을 사용하면, O(n^1.5)

 

지금까지 알려진 가장 좋은 성능을 보인 간격

-1, 4, 10 , 23, 57, 132, 301, 701, 1750(Marcin Ciura)

 

특성

- 입력 크기가 매우 크지 않은 경우에 매우 좋은 성능을 보임

- 임베디드(Embedded) 시스템에서 주로 사용

- H/W(간격에 따른 그룹 별 정렬 방식이 매우 적합)