[알고리즘] Divide & Conquer (2) - Merge sort

[2. Merge sort, 합병정렬]

※ 배열의 요소들을 정렬할 때 인접한 각 요소들을 비교하는 방식(bubble sort 등)의 성능 : O(n²)

따라서, 더 효율적일 수 있는 방법은 "분할정복"

● 방식

  → 정렬되지 않은 상태로 나열된 요소들의 집합을 절반으로 나누고

  → 각각의 분할된 집합을 정렬한 다음

  → 다시 결합한다

● 알고리즘

  → Divide : m = (s+e)/2 를 기준으로 더이상 분할할 수 없을때까지 절반으로 분할 O(n)

  → Conquer : 더 이상 분할할 수 없을 때 원소가 하나인 집합이므로, 정렬된 것으로 간주

  → Combine : 분할 후 각 집합들을 결합 O(logn)

  → Degenerate case : 원소가 하나인 경우 (s==e)

(* 배열A내에 원소가 n개인 경우 s=0, e=n-1)

● 구현

#include <stdio.h>
#include <stdlib.h>

void print(int A[]) {
	for (int i = 0; i < 8; i++)
		printf("%d, ", A[i]);
	printf("\n");
}

void Merge(int ls, int le, int rs, int re, int A[]) {
	int lptr = ls, rptr = rs, bptr = 0;
	int* temp = (int*)calloc((le - ls) + (re - rs) + 2, sizeof(int));
	while (lptr <= le && rptr <= re) {
		if (A[lptr] < A[rptr]) 
			temp[bptr++] = A[lptr++];
		else 
			temp[bptr++] = A[rptr++];
	}

	if (lptr > le)
		for (int i = rptr; i <= re; i++) 
			temp[bptr++] = A[i];
	if (rptr > re)
		for (int i = lptr; i <= le; i++) 
			temp[bptr++] = A[i];

	bptr = 0;
	for (int i = ls; i <= re; i++) 
		A[i] = temp[bptr++];
}

void Merge_sort(int s, int e, int A[]) {
	if (s == e)
		return;
	int m = (s + e) / 2;
	Merge_sort(s, m, A);
	Merge_sort(m + 1, e, A);
	Merge(s, m, m + 1, e, A);
}

int main() {
	int N, A[100];
	scanf_s("%d", &N);

	for (int i = 0; i < N; i++)
		scanf_s("%d", &A[i]);

	int s = 0, e = N - 1;
    
	Merge_sort(s, e, A);
	print(A);
}

● 성능

  → 입력받은 N개의 원소를 2개의 배열로 분할 : T(n/2)

  → 분할된 두 개의 배열을 각각 정렬해야 하므로 위의 T(n/2)를 두 번 반복 : 2*T(n/2)

  → n개의 원소를 각각 결합 : c*n

  → 따라서, T(n)=2*T(n/2)+O(n)

  → master theorm에 의해, O(nlogn)

 

※ 참고로, 정렬 과정은 아래와 같습니다