재시민

void InsertionSort(vector<int>& v, int f,int n, int h) {
	int i, j,temp;
	for (i = f + h;i < n;i+=h) { //h 만큼의 격차를 벌림 h가 작으면 작을수록 셸이 작아짐
		temp = v[i];
		for (j = i-h;f <= j && temp < v[j]; j -= h) {
			v[j + h] = v[j];// 셸의 개수만큼 반복하여 삽입정렬
		}
		v[j + h] = temp; //for 의 조건을 만족하지 못한다면 재할당
	}
}

void ShellSort(vector<int>& v, int n) {
	int i, h;
	for (h = n / 2;h > 0;h /= 2) {
		if (h % 2 == 0) h++;//2의 배수일 경우 1증가 맨마지막에 h 가 1일경우 존재위해
		for (i = 0;i < h;i++) InsertionSort(v, i, n , h);// i 값을 증가시키면서 셸 변경
	}
}

시간 복잡도 

최선시간 복잡도 O(n)

최악시간 복잡도 O(n1.5)

제자리성 : 제자리 정렬

안정성 : 불안정

인접하지 않은 원소끼리의 비교

알고리즘

1. h 의 격차를 두고 셀 설정

2. 셀 내부에서 삽입정렬

3. i 값을 늘리면서 셀 변경

4. for 문을 통해 다시 삽입정렬

5. for 문을 통해 h 변경