재시민

void countSort(vector<int>& v, int n) {
	vector<int> count(30, 0);// count 초기화
	int i;
	for (i = 0;i < n;i++) {
		count[v[i]]++;
	}
	for (i = 0;i < 30;i++) {
		for (int j = 0;j < count[i];j++) {
			printf("%d ", i);
		}
	}
}

제자리성 : 제자리 x

안정성 : 안정

(순서대로 배치)

시간 복잡도

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

알고리즘 

1. count 배열 초기화

2. 배열을 순회하여 배열의 인덱스 값에 해당하는 count index 에 ++

3. 이중 반복문 사용하여 count에 할당된 값만큼 index 값 출력

특정 배열에 대해 아주 빠르지만 count 에 할당되는 index 가 커지면 커질 수록 메모리 낭비가 매우심함

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. 설정된 피봇값을 중심으로 두개로 분할히여 퀵소트 진행