[Algorithm] Shell Sort

💡 동작원리

이 글에서는 Shell Sort(쉘정렬)에 대해 다뤄보려고 한다. Shell Sort는 Insertion Sort(삽입정렬)을 보완한 정렬로, Shell Sort의 원리는 Insertion Sort(삽입정렬)에 있다. Shell Sort는 정렬할 배열을 부분배열로 쪼개서 부분배열 각각에 대해 Insertion Sort을 실행하고, 배열을 합친 후 다시 또 쪼개서 Insertion Sort를 진행하고, 이 방법을 반복하여 배열을 정렬한다.

먼저 Shell Sort에서 배열을 어떻게 쪼개는지 살펴보자. 바로 간격을 두고 배열을 쪼개는 것이다. 이때 간격을 Gap(간격)이라고 부른다. 배열의 길이가 10이고 Gap이 5라고 가정하면 부분배열들의 인덱스는 {0,5}, {1,6}, ... {4,9}로 쪼개지는 것이다. 그리고 각각의 부분배열들에 대하여 모두 Insertion Sort를 실행한다. 이제 다시 Gap을 얼마로 두고 배열을 쪼갤 것인지 생각해보자. Shell Sort에서는 이전 Gap의 절반값으로 설정한다. 이때 Gap의 절반값이 짝수인 경우에는 (Gap/2 + 1)하여 홀수로 만들어준다. 그리고 쪼개진 부분배열들에 대하여 Insertion Sort를 진행한다. 이를 Gap이 1이 될 때까지 계속 반복하면 배열이 정렬된다. 아래 그림을 참고하자.

💻 코드

void New_Insertion_Sort(int Start, int Gap){
	for(int i = Start + Gap; i < N; i = i + Gap){
		int temp = Arr[i]; 
		int j;
		for(j = i - Gap; j >= Start; j = j - Gap){
			if(Arr[j] > temp) Arr[j + Gap] = Arr[j];
			else break;
		}
		Arr[j + Gap] = temp;
	}
}

void Shell_Sort(){
	for(int Gap = N/2; Gap > 0; Gap = Gap/2){
		if((Gap % 2) == 0) Gap++;
		for(int i = 0; i < Gap; i++){ New_Insertion_Sort(i, Gap); }
	}
}

위 코드는 Shell Sort(병합정렬)의 간단한 코드이다.

먼저 New_Insertion_Sort함수를 보자. Insertion Sort와 코드가 거의 똑같다. 다른점은 Gap을 추가하여 부분배열을 정렬한다는 점인데, 이에 대해서는 따로 설명하지 않겠다.

다음은 Shell_Sort함수이다. 반복문을 이용해서 Gap을 배열의 길이/2에서 시작하여 Gap이 1이 될때까지 New_Insertion_Sort함수를 실행시켜준다. 이때 Gap이 짝수이면 +1을 하여 홀수로 만들어준다.

⏱ 시간복잡도

Shell정렬의 시간복잡도는 최선의 경우, 최악의 경우, 평균적인 경우로 나뉜다. 각각 $O(N)$, $O(N^2)$, $O(N^{1.3,1.5})$이다.

Best case : $O(N)$
Worst case : $O(N^2)$
Average case : $O(N^{1.3,1.5})$