[자료구조론] C++ MergeSort (병합 정렬) 구현하기

#include <iostream>
using namespace std;

void printArray(int* S, int n) {
	for (int i = 0; i < n; i++) {
		cout << S[i] << ' ';
	}
	cout << endl;
}

void copy(int* S,int* U, int s, int e) {
	if (e == 1) {
		for (int i = 0; i < s; i++) {
			U[i] = S[i];
		}
	}
	else {
		for (int i = 0; i < s; i++) {
			U[i] = S[i + s];
		}
	}

}

void merge(int h, int m, int* U, int* V, int* S) {
	int i, j, k;
	i = 0; j = 0; k = 0;
	while (i <= h && j <= m) {
		if (U[i] < V[j]) {
			S[k] = U[j];
			i++;
		}
		else {
			S[k] = V[j];
			j++;
		}		
		k++;
	} 
	if (i > h) { // U의 탐색이 끝나고, V에 요소가 남았다면
		S[k] = U[j];
	}
	else if(j > m) {
		S[k] = V[i];
	}
}

void mergeSort(int n, int* S) {
	const int h = n / 2, m = n - h;

	int* U = new int[h];
	int* V = new int[m];
	if (n > 1) {
		copy(S, U, h, 1);
		copy(S, V, h, 0);
		mergeSort(h, U);
		mergeSort(m, V);
		
		merge(h, m, U, V, S);
	}
	
}

int main() {

	int n; cin >> n;

	int* arr = new int[n];
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}

	mergeSort(n, arr);

	printArray(arr, n);
}

 

#include <iostream>
#include <vector>
using namespace std;

vector <int> buff;

void __mergeSort(int a[], int left, int right) {
	if (left < right) {
		int center = (left + right) / 2;
		int p = 0; // 왼쪽 배열의 인덱스
		int i;
		int j = 0; // 오른쪽 배열의 인덱스
		int k = left;
		__mergeSort(a, left, center);
		__mergeSort(a, center, right);
		for (i = left; i < center; i++) {
			buff.at(p++) = a[i];
		} 
		while (i <= right && j < p) {
			a[k++] = (buff[j] <= a[i]) ? buff[j++] : a[i++];
		} 
		while (j < p)
			a[k++] = buff[j++];
	}
}

int mergeSort(int* a, int n) {
	__mergeSort(a, 0, n - 1);
	return 0;
}

void printArray(int* S, int n) {
	for (int i = 0; i < n; i++) {
		cout << S[i] << ' ';
	}
	cout << endl;
}

int main() {
	int n; cin >> n;
	int* arr = new int[n];
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	mergeSort(arr, n);
	printArray(arr, n);
	return 0;
}

위 코드는 자료구조 책에서 따온 코드이다. 

#include <iostream>
#include <algorithm>
using namespace std;

// start는 U 배열의 사이즈, end는 V 배열의 사이즈
void merge(int usize, int vsize, int S[], int U[], int V[]) {
	int i = 0, j = 0, k = 0;
	while (i <= usize && j <= vsize) {
		if (U[i] < V[j]) {
			S[k] = U[i];
			i++;
		}
		else {
			S[k] = V[j];
			j++;
		}
		k++;
	}
	if (i > usize) {
		// U 배열의 크기를 i가 초과하였을 때 (U 배열을 전부 순환함)

		// V의 남은 요소를 S에 대입한다. 
	}
	else if (j < vsize){
		// V 배열의 크기를 j가 초과하였을 때 (V 배열을 전부 순환함)


		// U의 남은 요소를 S에 대입한다. 
	}
}

void mergeSort(int* S, int start, int end) {
	int center = (start + end) / 2;
	
	int u_size = (end + 1) / 2;
	int* U = new int[u_size];
	// 0 ~ 6의 배열인 경우 = 3
	// 0 ~ 7의 배열인 경우 = 4
	if (end + 1 > 1) {
		copy(S + start, S + center, U);

		int v_size = end + 1 - (end + 1) / 2;
		int* V = new int[v_size];
		// 6 + 1 - (7 / 2) = 7 - 3 = 4
		// 7 + 1 - (8 / 2) = 8 - 4 = 4
		copy(S + center, S + end, V);
		// (S + 4, S + 6, V);
		// (S + 4, S + 7, V);

		mergeSort(S, start, center);
		mergeSort(S, center, end);

		merge(u_size, v_size, U, V, S);
	}
}


int main() {
	int arr[8] = { 27,10,12,20,25,13,15,22 };

	mergeSort(arr, 0, 7);

	for (int i = 0; i < 7; i++) {
		cout << arr[i] << " ";
	}
	return 0;
}

여기서 배열을 이용해 mergeSort를 구현하려고 했는데, 배열의 여러가지 내장함수를 사용하다 보니 vector가 더 편리하다고 판단되어 vector를 이용한 코드로 수정하기로 하였다.

 

vector로 U와 V 추가적인 배열을 설정하는 과정에서, 반복자 Iterator의 개념을 마주하였다. 

iterator 반복자를 사용해서 컨테이너에 저장된 원소를 순회하고 접근해 효과적으로 자료를 접근할 수 있는것이다. 

 

그래서 U와V 벡터를 새로 정의하면서, 값의 초기화를 S 벡터의 '절반'으로 각각 만드는 'subvector'의 개념을 사용하였다.

 

https://stackoverflow.com/questions/9705441/creating-a-new-c-subvector

Creating a new C++ subvector?

 

최종적으로 만들어진 코드는 다음과 같다. 

// start는 U 배열의 사이즈, end는 V 배열의 사이즈
template <typename T>
void Merge(ArrayVector <T>& S, int start, int center, int end) {
	ArrayVector<T> temp; // 병합된 요소를 담을 temporary Arrayvector
	int i = start;
	int j = center + 1;
	int k = 0; // temp의 인덱스를 나타냄.
	while (i <= center && j <= end) {
		if (S[i] <= S[j]) {
			temp.insert(k++, S[i++]);
		}
		else {
			temp.insert(k++, S[j++]);
		}
	}
	while (i <= center) {
		temp.insert(k++, S[i++]);
	}
	while (j <= end) {
		temp.insert(k++, S[j++]);
	}
	// copy
	for (int i = start; i <= end; i++) {
		S[i] = temp[i - start];
	}

}


template <typename T>
void MergeSort(ArrayVector<T>& S, int start, int end) {
	if (start < end) {
		int center = (start + end) / 2;
		MergeSort(S, start, center);
		MergeSort(S, center + 1, end);
		Merge(S, start, center, end);
	}
}