병합 정렬(Merge Sort)

• 병합 정렬(Merge sort)

배열을 앞부분과 뒷부분으로 나누어 각각 정렬한 후 둘을 병합하여 정렬하는 알고리즘

 

배열의 요소 개수가 2개 이상인 경우:

1. 앞부분을 병합 정렬로 정렬

2. 뒷부분을 병합 정렬로 정렬

3. 배열의 앞부분과 뒷부분을 병합 (두 배열의 요소를 하나씩 선택하여 비교한 후 작은 값을 대입)

 

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

static int* buff;  //작업용 배열

static 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 + 1, right);
		for (i = left; i <= center; i++) { //정렬된 앞부분을 buff에 저장
			buff[p++] = a[i];
		}
		while (i <= right && j < p) //뒷부분의 요소를 하나씩 앞부분과 비교해서 작은 것을 a에 추가
			a[k++] = (buff[j] <= a[i]) ? buff[j++] : a[i++];
		while (j < p) a[k++] = buff[j++]; //앞부분을 다 넣었으면 추가되지 못한 뒷부분의 요소를 순서대로 마저 추가
	}
}

int mergesort(int a[], int n) {
	if ((buff = calloc(n, sizeof(int))) == NULL) return -1;
	__mergesort(a, 0, n - 1);
	free(buff);
	return 0;
}

int main(void) {
	int i, nx;
	int* x;
	puts("병합 정렬");
	printf("요소 개수: ");
	scanf_s("%d", &nx);
	x = calloc(nx, sizeof(int));

	for (i = 0; i < nx; i++) {
		printf("x[%d]: ",i);
		scanf_s("%d", &x[i]);
	}

	mergesort(x, nx);
	puts("오름차순으로 정렬했습니다.");
	for (i = 0; i < nx; i++) printf("x[%d] = %d\n", i, x[i]);

	free(x);

	return 0;
}

 

시간복잡도: O(n log n) - best, avg, worst