8. 정렬

1. 버블 정렬 :

정렬 성능은 안좋지만 O(n^2) 빠르고 쉽게 구현 가능. 정렬이 중요한 문제가 아니라면 버블 정렬도 나쁘지 않음.

#define SWAP(a,b) {int t; t= b; b=a; a=t;}
int arr[5] = { 1,5,3,2,4 };
void bubble_sort(int arr_size) {
	for (int fixed_p = arr_size -1; fixed_p > 0; fixed_p--) {
		for (int bubble_p = 0; bubble_p < fixed_p; bubble_p++) {
			if (arr[bubble_p] > arr[bubble_p+1]) {	//5,3 일때 3,5로 바꿔줘야함
				SWAP(arr[bubble_p], arr[bubble_p+1]);
			}
		}
	}
}

#define SWAP(a,b) {int t; t=b; b=a; a=t; } 구문은 외워두고 활용하는게 좋음.

 

2. 병합 정렬 :

어떠한 경우에도 O(nlogn)의 성능을 가지지만 TEMP배열을 사용하기 때문에 메모리 낭비가 있음.

SWAP 과정이 없음.

int temp_arr[5];	//임시 배열 필요

void merge_sort(int start, int end) {
	if (start >= end) return;		//분할 종료 조건
	int mid = (start + end) / 2;	//arr을 반으로 나눌 기준값
	merge_sort(start, mid);			//반을 기준으로 왼쪽 분할 이 때 end는 중앙값이 됨.
	merge_sort(mid + 1, end);		//반을 기준으로 오른쪽 분할 이 때, start는 중앙값 +1이 됨
	int left_point = start;			//왼쪽 영역 시작 포인터
	int right_point = mid + 1;		//오른쪽 영역 시작 포인터
	int temp_point = start;			//임시 버퍼 시작 포인터

	while (left_point <= mid && right_point <= end) {
		if (arr[left_point] < arr[right_point]) temp_arr[temp_point++] = arr[left_point++];	//오른차순
		else temp_arr[temp_point++] = arr[right_point];
	}
	while (left_point <= mid) temp_arr[temp_point++] = arr[left_point++];		//남아 있는 왼쪽 영역을 임시 버퍼로
	while (right_point <= end) temp_arr[temp_point++] = arr[right_point++];		//남아 있는 오른쪽 영역을 임시 버퍼로

	for (temp_point = start; temp_point <= end; temp_point++) arr[left_point] = temp_arr[left_point];	//임시버퍼의 값을 원배열에 복사
}

 

3. 힙정렬 :

최댓값 최솟값을 바로 찾을 때 사용

push 연산과 pop 연산 때 힙트리를 유지하기 위해 특별한 연산 필요

maximum heap -> 내림차순

minimum heap -> 오름차순

힙트리 시작은 0이 아니라 1부터 시작. 0은 버림. 맨 마지막 노드가 어딘지 알아야함.

int heap_arr[6];	//힙트리는 1부터 시작
int heap_last_p = 0;	//힙트리의 마지막 노드를 가리킴

heap_push 는 자식이 부모를 타고 올라감

void heap_push(int data) {
	if (heap_last_p == 5 + 1) {
		//FULL일 때 더이상 못넣음.
		return ;
	}
	heap_arr[++heap_last_p] = data;	//heap트리는 전치연산을 함
	//마지막에 push 후 이 값이 부모보다 큰지(maximum heap) or 작은지(minimum heap) 비교
	int parent_p, children_p;
	children_p = heap_last_p;
	parent_p = children_p / 2;	//부모는 자식 index의 1/2
	//부모를 타고 올라가는 연산 필요.
	while (parent_p > 0) {
		//부모가 루트노드 일때 까지
		if (heap_arr[children_p] < heap_arr[parent_p]) {
			//minimum heap
			SWAP(heap_arr[children_p], heap_arr[parent_p]);
			//자식 index가 부모 index가 됨. (부모 타고 올라가기)
			children_p = parent_p;
			parent_p = children_p / 2;
		}
		else {
			//이미 자식이 부모보다 크면 루트노드가 될 수 없음
			break;
		}
	}
}

heap_pop은 부모가 자식을 타고 내려옴

void heap_pop(int* data) {
	//EMPTY조건 체크
	if (heap_last_p == 0) {
		return;
	}
	//루트노드 heap_arr[1]를 pop
	*data = heap_arr[1];
	//맨 마지막 노드를 루트노드에 올림
	heap_arr[1] = heap_arr[heap_last_p--];
	//push와 반대로 부모에서 자식으로 내려가기 연산 필요
	int parent_p, children_p, left_children_p, right_children_p;
	//처음
	parent_p = 1;
	left_children_p = parent_p * 2;
	right_children_p = left_children_p + 1;
	//왼쪽 자식이 더이상 없을 때까지 내려가면서 비교. heap_last_p는 heap배열의 끝.
	while (left_children_p <= heap_last_p) {
		//내려왔더니 자식이 하나 뿐일 때
		if (left_children_p == heap_last_p) {
			//자식이 하나뿐이니 children_p에 그냥 넣는다.
			children_p = left_children_p;
		}
		else {
			//자식이 둘이면 둘 중 더 작은 것을 선택해야 한다.
			if (heap_arr[left_children_p] < heap_arr[right_children_p]) {
				children_p = left_children_p;
			}
			else {
				children_p = right_children_p;
			}
		}
		//자식을 선택 했다면 부모와 비교한다
		if (heap_arr[children_p] < heap_arr[parent_p]) {
			//부모가 더 크면 SWAP
			SWAP(heap_arr[children_p], heap_arr[parent_p]);
			//부모 다시 설정 후 자식 타고 내려가기 반복
			parent_p = children_p;
			left_children_p = parent_p * 2;
			right_children_p = left_children_p + 1;
		}
		else break;
	}
}

main에서 사용방법 : pop 할 때 나오는 값을 list에 따로 저장한다면 그게 바로 heap 정렬

	//heap push
	for (int i = 0; i < 5; i++) {
		heap_push(arr[i]);
	}
	//heap pop
	int data;
	for (int i = 0; i < 5; i++) {
		heap_pop(&data);
		printf("%d\n", data);
	}

4. 퀵정렬 :

void quick_sort(int s, int e) {
	if (s >= e) return; //종료 조건
	int left_p = s, target_p = s, pivot_p = e;	//pivot은 end로 잡아줘야 구현 쉽다.
	for (; left_p < e; left_p++) {
		if (arr[left_p] < arr[pivot_p]) {
			//pivot은 비교 대상 pivot보다 작으면 target_p과 교환이 이루어짐
			//left_p 위치와 target_p 위치가 같으면 안됨
			if (left_p != target_p) SWAP(arr[left_p], arr[target_p]);
			target_p++;
		}
	}
	if (target_p != pivot_p) SWAP(arr[target_p], arr[pivot_p]);
	quick_sort(s, target_p - 1);
	quick_sort(target_p + 1, e);
}