정렬 (8) - 쉘 정렬 (Shell Sort)

1. 알고리즘 개요

• 삽입정렬(Insertion Sort)는 거의 정렬된 데이터에 한해서는 매우 빠르다는 특징이 있음.
• 삽입정렬의 문제 : 비교/교환이 너무 자주 일어난다는 단점이 존재함.
• 문제 해결 : H-Sort 기법을 이용하는 것. 이 것을 Shell Sort라고 함.
• 시간 복잡도 : $O(n \times (logn)^2)$ 혹은 $O(N^{1.25})$ 정도로 평가됨.
• $O(n logn)$보다는 느리지만, 멀리 떨어진 자료를 교환해서 데이터에 둔감 (영향 ↓)

 

2. H-Sort (H Elements Sort)

• H-Sort : Gap이 H인 Element(부분집합)만 뽑아서 Insertion Sort를 진행하는 것.
• H-Sort를 반복하면 배열 전체가 점점 조금씩 정렬되는 효과가 있음.
• 삽입정렬은 거의 정렬된 데이터에 한해서 매우 빠르게 정렬되기 때문에 속도가 크게 향상됨
• H-Sort의 핵심은 Gap(간격)을 얼마로 설정할지인데, 아래예시는 간격을 1/2로 설정하였음.
• 아래 예시는 10개의 원소를 정렬하는 예시로 H = 5, 2, 1이 된다. [0, 5], [1, 6], ... [4, 10]를 삽입정렬하고 [0, 2, 4, 8, 10], [1, 3, 5, 6, 9]를 삽입정렬하고 최후에는 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]를 삽입정렬한다. 절차가 복잡해서 기존 삽입정렬보다 느릴 것 같아보이지만 데이터를 정렬에 가까운 상태로 만들어놓고 삽입정렬하기 때문에 실제로는 매우 빠르다.

 

 

3. 소스코드

#include<stdio.h>

// 오리지날 insertion sort 함수. 비교를 위해 작성 
void original_insertion_sort(int *arr, int size){
	
	for(int i = 1 ; i < size ; i++){
		int curr = arr[i];
		int j = i-1;
		
		for(; j >= 0 && curr < arr[j]; j--){
			arr[j + 1] = arr[j];
		}
		
		arr[j + 1] = curr;
	}
}

// shell sort 전용 insertion sort 함수.
// start와 gap을 추가로 더 입력받음 
void interval_insertion_sort(int *arr, int size, int start, int gap){
	// 0 → start 
	// 1 → gap
	// 위 처럼 바꾸면 대강 비슷함.
	
	for(int i = gap ; i < size ; i += gap){
		int curr = arr[i];
		int j = i - gap; 
		
		for(; j >= start && curr < arr[j] ; j -= gap){
			arr[j + gap] = arr[j];
		}
		
		arr[j + gap] = curr;
	}
}

void shell_sort(int *arr, int size){
	
	for(int gap = size/2 ; gap > 0 ; gap /= 2){
	// gap이 0이 되기 전까지 계속 작아짐
		
		for(int i = 0 ; i < gap ; i++){
		// i=0 → [0, 5] / i=1 → [1, 6] / ...
			
			interval_insertion_sort(arr, size, i, gap);
		}
	} 
}

int main(){
	int arr[] = {2, 4, 0, 1, 3, 5, 7, 6, 9, 8};
	int size = sizeof(arr)/sizeof(arr[0]);
	shell_sort(arr, size);
	
	for(int i = 0 ; i < size ; i++){
		printf("%d ", arr[i]);
	}
	
	return 0;
}

 

4. Reference