[C++] Merging Sort

1. 병합 정렬

: Divide Conquer 기법 이용

 

1-1. 병합 정렬 알고리즘 동작 과정

• 재귀문을 돌며 주어진 배열들을 단말노드로 될 때까지 Divide

void MergeSort(int * arr, int * tmp, int start, int end) {
	
	if (start < end) {
		int mid = (start + end) / 2;

		MergeSort(arr, tmp, start, mid);
		MergeSort(arr, tmp, mid + 1, end);
		Merge(arr, tmp, start, mid, end);
	}
}

 

• 분리된 배열들을 정렬하며 합치는 과정

void Merge(int* arr, int* tmp, int start, int mid, int end) {

	int idx = start;
	int left = start;
	int right = mid + 1;

	for (int i = start; i <= end; i++) {
		tmp[i] = arr[i];
	}

	while (left <= mid && right <= end) {
		if (tmp[left] <= tmp[right]) {
			arr[idx++] = tmp[left++];
		}
		else {
			arr[idx++] = tmp[right++];
		}
	}

	while (left <= mid) {
		arr[idx++] = tmp[left++];
	}
	while (right <= end) {
		arr[idx++] = tmp[right++];
	}
}

1-2. 전체 소스 코드 

#include <iostream>
using namespace std;

void Merge(int* arr, int* tmp, int start, int mid, int end) {

	int idx = start;
	int left = start;
	int right = mid + 1;

	for (int i = start; i <= end; i++) {
		tmp[i] = arr[i];
	}

	while (left <= mid && right <= end) {
		if (tmp[left] <= tmp[right]) {
			arr[idx++] = tmp[left++];
		}
		else {
			arr[idx++] = tmp[right++];
		}
	}

	while (left <= mid) {
		arr[idx++] = tmp[left++];
	}
	while (right <= end) {
		arr[idx++] = tmp[right++];
	}
}

void MergeSort(int * arr, int * tmp, int start, int end) {
	
	if (start < end) {
		int mid = (start + end) / 2;

		MergeSort(arr, tmp, start, mid);
		MergeSort(arr, tmp, mid + 1, end);
		Merge(arr, tmp, start, mid, end);
	}
}



int main() {

	int arr[] = { 4,2,6,3,7,8,5,1 };
	int size = sizeof(arr) / sizeof(int);
	int* tmp = new int[size];
	
	cout << "[원본 배열 출력]\n";
	for (auto element : arr) {
		cout << element << " ";
	}

	MergeSort(arr, tmp, 0, size-1);

	cout << "\n\n[Merge Sort 결과 배열 출력]\n";
	for (int i = 0; i < size; i++) {
		cout << arr[i] << " ";
	}




	getchar();
	return 0;
}