[알고리즘] 병합정렬 (Merge sort)

 

설명

병합정렬의 원리는, 

1. 배열의 사이즈가 1이 될 때까지 반으로 쪼갠다

2. 사이즈가 1이 되면, 오름차순(혹은 내림차순)으로 비교 정렬하여 합친다.

3. 이것을 반복한다.

결과적으로 이것의 시간복잡도는 Nlog(N)이 된다.

 

핵심코드

int arr[N], trr[N];

void mergeSort(int *arr, int s, int e) {
	if (s + 1 >= e) return;
	int m = (s + e) / 2, i = s, j = m, k = s;
	mergeSort(arr, s, m), mergeSort(arr, m, e);

	while (i < m && j < e) {
    	// 오름차순이므로, arr[j]가 더 작으니, arr[j]를 먼저 채운다.
		if (arr[j] < arr[i]) trr[k++] = arr[j++];
		else trr[k++] = arr[i++];
	}
    
    // 위를 거쳤는데도 아직까지 i가 m보다 작다면, 아직 i가 덜 합쳐진 것이다. 따라서 arr[i]를 trr[i]로 합쳐준다.
	while (i < m) trr[k++] = arr[i++];
	while (j < e) trr[k++] = arr[j++];
    
    // arr배열을 업데이트 해준다.
	for (i = s; i < e; ++i) arr[i] = trr[i];
}

 

소스코드 (C++)

#include <stdio.h>

constexpr int N = 10;

// arr은 정렬하고자하는 배열
// trr는 병합정렬을 위한 임시 배열
int arr[N], trr[N];

void mergeSort(int *arr, int s, int e) {
	if (s + 1 >= e) return;
	int m = (s + e) / 2, i = s, j = m, k = s;
	mergeSort(arr, s, m), mergeSort(arr, m, e);

	while (i < m && j < e) {
		if (arr[j] < arr[i]) trr[k++] = arr[j++];
		else trr[k++] = arr[i++];
	}
	while (i < m) trr[k++] = arr[i++];
	while (j < e) trr[k++] = arr[j++];
	for (i = s; i < e; ++i) arr[i] = trr[i];
}

int main(void) {
	
	int a[] = { 10, 1, 3, 2, 5, 4, 6, 9, 7, 8 };

	mergeSort(a, 0, N);

	for (int i = 0; i < N; i++) {
		printf("%d ", a[i]);
	}
	printf("\n");
	return 0;
}

 

출력화면

1 2 3 4 5 6 7 8 9 10

 

 

소스코드 (C++) (구조체 선언 후 <연산자 재정의하는 경우)

#include <stdio.h>

constexpr int N = 10;

// arr은 정렬하고자하는 배열
// trr는 병합정렬을 위한 임시 배열
struct Product {
	int id;
	int price;

	bool operator<(const Product&t) const {
		return price < t.price;
	}
} arr[N], trr[N];

void mergeSort(Product *arr, int s, int e) {
	if (s + 1 >= e) return;
	int m = (s + e) / 2, i = s, j = m, k = s;
	mergeSort(arr, s, m), mergeSort(arr, m, e);

	while (i < m && j < e) {
		if (arr[j] < arr[i]) trr[k++] = arr[j++];
		else trr[k++] = arr[i++];
	}
	while (i < m) trr[k++] = arr[i++];
	while (j < e) trr[k++] = arr[j++];
	for (i = s; i < e; ++i) arr[i] = trr[i];
}

int main(void) {
	
	Product a[] = { 
		{1, 10},
		{2, 1},
		{3, 3},
		{4, 2},
		{5, 5},
		{6, 4},	
		{7, 6},
		{8, 9},
		{9, 7},
		{10, 8}
	};

	mergeSort(a, 0, N);

	for (int i = 0; i < N; i++) {
		printf("%d ", a[i].price);
	}
	printf("\n");
	return 0;
}

 

 

 

출력화면

1 2 3 4 5 6 7 8 9 10

 

관련 문제

백준 2751번 https://www.acmicpc.net/problem/2751

정올 3519번 https://jungol.co.kr/problem/3519