[알고리즘] 2원 합병 정렬 merge sort

2원 합병 정렬

• 주요 특징
  • 대표적인 분할 및 정복 기법
  • 자료를 거의 동일한 크기의 두 그룹으로 나누고, 각각을 별도로 정렬한 후, 합병
  • 순환 알고리즘 방식
• 복잡도분석
  • 합병(merge)에 따른 비교회수 : n번 = O(n)
  • 순환방정식 : T(n) = 2 T(n/2) + n
  • 전체 비교 회수 : O(n log n)
• 장단점 
  • 수행 시간 우수, 단 순환 알고리즘의 한계 내포
  • 추가 기억장소 사용량 : 추가 배열용 n개 필요
    • 전체 총 2n개의 기억장소 필요, O(n)

 

void merge_sort(data A[], int L, int R) {
	int m;
	if(R > L) {
		m = (R+L) / 2; 
        merge_sort(A, L, m); 
        merge_sort(A, m+1, R); 
        merge(A, L, R, m);
	} 
}

 

• 비교회수 분석 : T(n) = 2 * T(n/2) + n = O(n*log n)
• 기억장소 사용량 : 2*n (배열 2개)

 

merge sort를 활용한 예제

#include <iostream>
using namespace std;

const int SIZE = 15;
int L[SIZE] = { 10, 4, 7, 1, -2, 12, 28, 66, 9, 3, 5, 7, 6, 21, 11 };


void print_data()
{
	for (int i = 0; i < SIZE; i++)
		cout << " " << L[i] << " ";
	cout << endl;
}

void merge(int L[], int left, int mid, int right)
{
	int i, j, k;

	i = left;
	j = mid + 1;
	k = left;

	int tmp_arr[SIZE];

	while (i <= mid && j <= right) {
		if (L[i] <= L[j]) {
			tmp_arr[k] = L[i];
			i++;
		}
		else {
			tmp_arr[k] = L[j];
			j++;
		}
		k++;
	}


	if (i > mid) {
		for (int m = j; m <= right; m++) {
			tmp_arr[k] = L[m];
			k++;
		}
	}
	else {
		for (int m = i; m <= mid; m++) {
			tmp_arr[k] = L[m];
			k++;
		}
	}

	for (int m = left; m <= right; m++) {
		L[m] = tmp_arr[m];
	}
}

void merge_sort(int a[], int left, int right) {
	int mid;

	if (left < right) {
		mid = (left + right) / 2;
		merge_sort(a, left, mid);
		merge_sort(a, mid + 1, right);
		merge(a, left, mid, right);
	}
}


void main()
{
	cout << "Input Data : ";
	print_data();

	/* sort the elements of array L[] in ascending order */
	merge_sort(L, 0, SIZE - 1);

	cout << "\n\nSorted Data : ";
	print_data();

}