재시민

void heapify(vector<int>& v, int size, int i) {
	int c = 2 * i + 1; // 왼쪽자식 선택
	if (c < size - 1 && v[c] < v[c + 1]) c++; //오른쪽자식 존재하면서, 오른쪽자식이 더크면 오른쪽 자식 선택
	if (c < size && v[i] < v[c]) swap(v[i], v[c]); // 부모보다 자식이 더크면 둘이 바꿈
	if (c < size / 2) heapify(v, size, c); //내부노드에서 한정하여 반복
}

void heapSort(vector<int>& v, int size) {
	for (int i = size / 2;i >= 0;i--) {
		heapify(v, size, i);
	}
	for (int i = size - 1;i >= 0;i--) {
		swap(v[i], v[0]);//힙이 만들어지고 맨처음값과 맨 뒷 값 변경
		heapify(v, i, 0);// 사이즈 조절 후 
	}
}

제자리성 : 제자리 정렬

시간복잡도

최악시간 복잡도 = O(nlogn) (완전 이진트리)

알고리즘

1. 전체 이진트리로 만들기

2. 서브트리마다 최대 힙구조로 만들기

3. 맨 첫번째 원소와 마지막 원소를 스왑

4. 위의 과정 반복 

void merge(vector<int>& v, int left, int mid, int right) {
	int i, j, k, l;
	i = left; j = mid + 1; k = left;
	while (i <= mid && j <= right) {
		if (v[i] <= v[j]) sorted[k++] = v[i++]; //더 작은 값을 새로운 배열로 할당
		else sorted[k++] = v[j++];
	}
	if (i > mid)// mid 값을 넘었으므로 right까지의 남은 j 원소들을 새로운배열에 옮김
		for (l = j; l <= right;l++) sorted[k++] = v[l];
	else for (l = i;l <= mid;l++) sorted[k++] = v[l];//j > right
	for (l = left; l <= right;l++) v[l] = sorted[l];// 새로운 배열을 다시 원래배열로 옮김
	return;
}

void mergeSort(vector<int>& v, int left, int right) {
	int mid = (left + right) / 2; 
	if (left < right) {
		mergeSort(v, left, mid);
		mergeSort(v, mid + 1, right);
		merge(v, left, mid, right);
	}
}

시간 복잡도

평균 시간복잡도 = O(nlogn)

제자리성 : 제자리 x (추가 배열 사용)

알고리즘 

1. left, right의 중간인 mid 값 설정

2. i, j 를 증가시키면서 각 인덱스의 비교를 통해 더 작은 값을 sorted 배열에 삽입

3. 먼저 끝나는 쪽의 반대쪽에서 남은 부분은 sorted 에 순서대로 삽입

int partition(vector<int>& v, int left, int right) {
	int pivot, temp, low, high;
	low = left;
	high = right+1 ;
	pivot = v[left];
	
	do {
		do {
			low++;
		} while (low <= right && v[low] < pivot);// low right 만나지 않거나 같고, v[low] 값이 피봇 보다 작다면 반복
		do {
			high--;
		} while (high >= left && v[high] > pivot);// high left 만나지 않거나 같고, v[high] 값이 피봇보다 크다면 반복
		if (low < high) {
			swap(v[low], v[high]);
		}
	} while (low < high);

	swap(v[left], v[high]);
	return high;
}
void QuickSort(vector<int>& v,int left, int right) {
	if (left < right) {
		int q = partition(v, left, right);
		QuickSort(v, left, q - 1);
		QuickSort(v, q + 1, right);
	}
	
}

제자리성 : 제자리 정렬 (순환호출로 인해 제자리가 아니라고도 할 수 있음)

안정성 : 불안정 (swap)

시간 복잡도

평균시간 복잡도 = O(nlogn) (분할 과정이 트리와 비슷하여 트리의 높이 만큼 곱해진다.)

최악시간 복잡도 = O(n2)

알고리즘

1. low, high 값을 늘리고, 줄이면서, 설정된 피봇 값보다 크거나 작다면 멈춘다.

2. 이때 low < high 이면 v[low], v[high] 스왑

3. do-while 종료 후 기존의 피봇값과 high 값을 변경하여 피봇 재설정

4. 설정된 피봇값을 중심으로 두개로 분할히여 퀵소트 진행

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 변경