[lecture] 6주차.정렬 알고리즘_쉘 정렬

버블 정렬이나 삽입 정렬이 수행되는 과정은 '작게' 이웃하는 원소의 자리바꾸기이다. 버블 정렬의 수행 과정은 작은(가벼운) 숫자가 배열의 앞부분으로 매우 느리게 이동하며, 삽입 정렬에서 마지막 원소가 가장 작은 숫자라면 그 숫자가 배열의 맨 앞으로 이동해야 하므로 모든 다른 숫자들이 1칸씩 오른쪽으로 이동해야 한다. 쉘 정렬은 이를 이용한 것이다.

쉘 정렬

쉘 정렬은 삽입 정렬을 이용하여 배열 뒷부분의 작은 숫자를 앞부분으로 '빠르게' 이동시키고, 동시에 앞부분의 큰 숫자는 뒷부분으로 '빠르게' 이동시킨다.

쉘 정렬은 gap 을 이용해 정렬한다. 점점 간격을 작게(마지막으로 1) 해서 타그룹에 속해 서로 비교되지 않은 숫자를 찾는데 여기서 모든 원소를 1개의 그룹으로 여기는 것을 삽입 정렬이라고 볼 수 있다.

//shell sort
입력 : 크기가 n인 배열 A
출력 : 정렬된 배열 A
for each gap h = [h0 > h1 > ... > hk = 1]	//큰 gap부터 차례로 루프 돌리기
	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을 사용하면 O(n^1.5)이다.

지금까지 알려진 가장 좋은 성능을 보인 간격은 Marcin Ciura이고, [1,4,10,23,57,132,301,701,1750]이다.

쉘 정렬의 시간복잡도는 가장 좋은 간격을 알아내야 하는 것이 선행되어야 하기 때문에, 아직 풀리지 않은 문제이다.

쉘 정렬의 특성

쉘 정렬은 입력 크기가 매우 크지 않은 경우에 매우 좋은 성능을 보인다. 쉘 정렬은 임베디드(Embedded) 시스템에서 주로 사용하고 쉘 정렬의 특징인 간격에 따른 그룹 별 정렬 방식이 H/W로 정렬 알고리즘을 구현하는데 매우 적합하다.