[Algorithm] Shell Sort

정렬이란, 임의의 순서가 있는 데이터가 무작위로 주어졌을 때 이를 순서대로 나열하는 것을 의미한다. 정렬 방식은 여러가지가 있으며 오늘은 그 중 Shell Sort에 대해 알아보자.

Insertion Sort

기본 개념

Shell sort를 알기 위해서는 Insertion Sort부터 알아야한다. Insertion Sort 는 이미 정렬된 상태에 새로운 데이터의 위치를 찾아 넣는 방식이다. 

위 이미지에서 파란 부분이 이미 정렬된 부분, 붉은 부분이 새로 넣고자 하는 원소이다. 붉은 원소를 파란 부분의 어느 위치에 넣을 것인지 찾아 '삽입'하는 형태로 정렬을 진행하기 때문에 '삽입 정렬'이라고 부른다. 

 

코드

# input : 정렬되지 않은 list
# output : 정렬된 list
def insertionsort(a):
    for i in range(1, len(a)):
    	key = a[i]
        j = i-1
        while j >=0 and a[j] > key:
        	a[j+1] = a[j] # key가 더 작으면 옆으로 값 밀기
            j-=1
        a[j+1]=key
	return a

 

시간복잡도

Insertion sort는 이미 정렬된 상태이거나 거의 정렬된 상태인 경우 매우 좋은 성능을 낸다.

입력 데이터	대소 비교	Swap
이미 정렬된 상태 (best case)	N-1	0
반대 방향 정렬 (worst case)	~ N^2 /2	~ N^2 /2
절반정도 정렬 (avg)	~ N^2 / 4	~ N^2 / 4

 

특히, 이미 정렬된 상태에 가까울 때 swap 횟수가 많이 줄어든다. insertion sort는 Inversion 수에 따라 swap을 진행한다.

• Inversion
  정렬 순서가 어긋난 쌍을 의미한다.
  A E E L M O T R X P S 의 경우 T-R, T-P, T-S, R-P, X-P, X-S 가 정렬 순서가 어긋난 쌍, 즉 Inversion이다.
  따라서 위 경우는 Insertion Sort를 실행하면 6번 Swap을 수행한다. ( 이 말이 진짜 바꾸는 것을 6번 하는게 아니라 원소를 비교하면서 위치까지 도달하여 swap을 하는 것을 6번 한다는 것이다. )

 

h-sort

기본 개념

모든 h 만큼 떨어진 원소끼리 정렬된 상태로 만드는 것이다. h의 값이 커질수록 실행해야하는 연산량이 줄어들지만 h가 작을 수록 더 완전한 정렬 결과를 보인다.

1-sort는 insertion sort와 동일한 결과를 도출한다.

코드

def hInsertionSort(a, h):
	for i in range(h, len(a)):
    	key = a[i]
        j = i - h # h 간격으로 진행
        while j >=0 and a[j] > key:
        	a[j+h] = a[j]
            j-=h
        a[j+h] = key
    return a

 

Shell Sort

기본 개

shell sort는 h-sort를 h 값을 점점 감소시키면서 최종적으로 1-sort를 진행하여 정렬된 상태로 만드는 것이다. 

이 방식으로 하면 여러 칸 앞으로 가야하는 원소들을 한 번에 이동시키기 때문에 1-sort 하기 전 inversion을 크게 줄여주기 때문에 마지막 정렬이 ~N 에 비슷해진다. 또한, 각각의 h-sort를 진행할 때 생각보다 비교 횟수가 많지 않다는 것을 직접 해보면 알게 될 것이다.

 

h-sort의 h 값은 어떻게 정할까?

가장 대중적인 방법은 Donald Knuth가 제안한 3x+1 방식이다.

1 <-4 <-13 <-40 <-121 ...

계산하기 쉽고 준수한 성능을 낸다고 한다.

+) 이 외에도 2^k +1, 프린스턴 대학 Sedgewick 교수가 제안한 수열 등 다양한 방식이 있다.

하나 중요한 점은 어떤 수의 배수로는 잘 진행하지 않는다. 특히 2^k 는 짝수만 계속 진행하기 때문에 매우 좋지 않다.

 

코드

Knuth가 제안한 3x + 1 방식을 이용해 h를 정했다.

def shellSort(a):
	N = len(a)
    h = 1
    while h < N/3: # N을 넘지 않는 h를 구한다.
    	h = 3 * h +1
    
    while h >= 1:
    	hInsertionSort(a, h) # h-sort 진행
        h = h //= 3

 

시간복잡도

Shell Sort의 성능을 표현할 수 있는 수학적 모델을 아직 찾지 못했다. h = 3x+1를 사용하는 경우 ~logN회의 h-sort를 수행하기 때문에 ~NlogN으로 추측하고 있다.