Kim-Baek 개발자 이야기

병합 정렬 (Merge Sort) 본문

컴퓨터 공학/자료구조, 알고리즘

병합 정렬 (Merge Sort)

킴백 개발자 2020. 9. 27. 11:13

Merge Sort는 Divide and Conquer 알고리즘 기법이다.

 

  • Merge Sort의 경우 항상 O( N log(N) ) 의 시간복잡도를 가진다.

 

  • 성능은 전반적으로 Quick Sort 에 비해 떨어진다.

 

  • Stable 하다

 

  • 추가 메모리 공간(Not in-place)이 필요하다.

 

  • C++의 stable_sort  Merger Sort 로 구현되어 있다.

 

 

#include <iostream>

using namespace std;

void merge_sort(int ary[], int left, int right);
void merge(int ary[], int left, int mid, int right);

int* temp;

int main() {
	int ary[] = { 6,4,2,7,9,7,6,4,4,1,0 };
	temp = new int[11];
	for (int i = 0; i < 11; i++)
		cout << ary[i] << ' ';
	cout << endl;
	merge_sort(ary, 0,10 );
	for (int i = 0; i < 11; i++)
		cout << ary[i] << ' ';
	return 0;
}


void merge_sort(int ary[], int left, int right) {
	if (left < right) {
		int mid = (left + right) / 2;
		merge_sort(ary, left, mid);
		merge_sort(ary, mid+1, right);
		merge(ary, left, mid, right);
	}
}

void merge(int ary[], int start, int middle, int end) {
	int mid = (start + end) / 2;
	int i = start;
	int j = mid + 1;
	int k = start;
	while (i <= middle && j <= end) {
		if (ary[i] < ary[j])
			temp[k++] = ary[i++];
		else
			temp[k++] = ary[j++];
	}
	if (i > mid) {
		for (int it = j; it <= end; it++)
			temp[k++] = ary[it];

	}
	else {
		for (int it = i; it <= mid; it++)
			temp[k++] = ary[it];
	}
	for (int i = start; i <= end; i++)
		ary[i] = temp[i];
}

 

반응형

'컴퓨터 공학 > 자료구조, 알고리즘' 카테고리의 다른 글

힙 정렬 (Heap Sort)  (0) 2020.09.29
퀵 정렬 (Quick Sort)  (0) 2020.09.28
삽입 정렬 (Insertion Sort)  (0) 2020.09.26
선택 정렬 (Selection Sort)  (0) 2020.09.25
BFS (Breath First Search)  (0) 2020.09.23
Comments