재시민

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 에 순서대로 삽입

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

void InsertionSort(vector<int>& v, int n) {
	int i, j,temp;
	for (i = 2;i < n;i++) { //v[0] = -1 더미값 세팅
		temp = v[i];
		j = i;
		while (v[j - 1] > temp) { //이전 값과 비교 후 크면 스왑
			swap(v[j], v[j - 1]);
			j--;
		}
	}
}

void insertionSort(vector<int>& v, int n) {
	int i, j;
	for (i = 1; i < n; i++) {
		for (j = i; j >0;j--) {
			if (v[j] < v[j - 1]) swap(v[j], v[j - 1]);
		}
	}
}

알고리즘

1. v[0] 에 더미값 세팅 

2. 삽입할 값 temp 에 저장

3. temp 값과 temp 이전 값들과 비교후 크면 스왑

void bubbleSort(vector<int>& v, int n) {
	int i, j,temp;
	for (i = n-1; i > 0;i--) {// n-1 완료되면 가장큰수 배열의 맨 끝에 위치 다음 n-2,n-3...,1
		for (j = 0;j < i;j++) {
			if (v[j] > v[j + 1]) swap(v[j], v[j + 1]);
		}
	}
}

for 문 한번 돌때마다 가장 큰 수가 맨 뒤에 위치하게 된다.

따라서, 매 회 n-i 순회 하며

안정성 : 안정된 정렬 (인접한 레코드끼리만 자리바꿈)

제자리성 : 제자리 정렬

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

최악시간복잡도 = O(n2) (역순으로 정렬)

알고리즘

1. 첫번째 for 에서 i 의 크기를 n-1 부터 순회

2. 두번째 for 에서 j 를 i 까지 순회하면서 v[j] > v[j+1] 이면 swap