[Sort]Shell Sort

- 삽입 정렬을 보완한 정렬 알고리즘

 

- 삽입 정렬의 단점은 비효율적으로 값의 교환 횟수가 많아질 수 있다는 점이다.  

  ex) 10개의 배열 요소 중, 8번째 값을 정렬된(왼쪽) 리스트에 삽입할 위치를 찾기 위해 그만큼 비교 연산을 해야함.

 

- 쉘 정렬은 이러한 삽입 정렬의 단점을 보완하여 정렬할 배열을 여러개의 부분 배열로 나누어 나누어진 배열에 대해 삽입 정렬을 수행한다. 따라서 서로 멀리 떨어진 요소들간의 비교 연산또한 효율적으로 할 수 있다.

 

- 쉘 정렬은 중간 크기의 목록에 효율적. 병합, 힙, 퀵 정렬보다는 현저히 느리지만 속도가 우선시 되지 않는 5천개 정도의 요소를 가진 목록에는 좋을 수 있음

 

-  셸 정렬에서는 요소들이 멀리 떨어진 위치로 이동할 수 있다는 장점이 있다. 이런 것이 가능한 이유는 셸 정렬이 전체의 배열(리스트)을 한 번에 정렬하지 않는다는 점 때문이다. 대신 먼저 정렬해야 할 리스트를 일정한 기준에 따라 분류하여 연속적이지 않은 여러 개의 부분 리스트를 만들고, 각 부분 리스트를 삽입 정렬을 이용하여 정렬한다.

출처: https://mattlee.tistory.com/76 [waca's field]

 

- 시간 복잡도

   Worst: O(nlog^2n)

   Best: O(n)

   Average: 증분 시퀀스에 따라 다름

   

- 공간 복잡도: O(n)

void insertion_sort_shell(int arr[],int start, int last, int gap) {

	for (int i = start + gap; i <= last; i += gap) {
		int key = arr[i]; 
		int j = i;

		while (arr[j - gap] > key && j >= start) {
			arr[j] = arr[j - gap];
			j -= gap;
		}
		arr[j] = key;

	}
	
}

void shell_sort(int arr[], int size_arr) {

	int gap = size_arr / 2;
	while (gap >= 1) {
		if (gap % 2 == 0) {
			gap += 1;
		}

		for (int i = 0; i < gap; i++) {
			insertion_sort_shell(arr,i, size_arr - 1, gap);
		}
		
		
		gap /= 2;
	}
	print_arr(arr, size_arr);
}