[Algorithm] C++ Merge Sort (병합정렬)

📚 Computer Science/Algorithm

[Algorithm] C++ Merge Sort (병합정렬)

스쳐가는비 2022. 10. 5. 20:23

병합정렬

List를 반으로 더이상 나눌 수 없을때까지 반으로 나누고(Divide - 분할),
나누어진 부분 List들을 두개씩 짝지어 정렬(Conquer - 정복)하며 합치는(Combine - 결합)과정을 반복하는 방법

병합정렬 알고리즘

하나의 List를 더 이상 나눠질 수 없을 때 까지 반으로 분할한다.
더 이상 나눌 수 있는 List가 없을 경우, 반복적으로 나뉘어진 부분 List들을 정렬하며 합친다.

예시

출처 - https://runestone.academy/ns/books/published/pythonds/SortSearch/TheMergeSort.html

병합정렬의 알고리즘은 기본적으로 분할정복을 사용한다.

원소들의 List를 계속하여 나뉘어지지 않을때 까지 반으로 나누는 재귀 알고리즘을 이용한다.

원소 List에 둘 이상의 원소가 있는 경우 List를 분할하고, 양쪽 절반에 대해 병합정렬을 재귀적으로 호출하여 진행한다.

아래의 그림은 분할한 원소들을 다시 병합하는 과정을 보여준다.

위의 그림은 두 개의 정렬된 List들을 가져와 하나의 정렬된 새 List로 결합하는 과정이다.

분할된 원소들을 비교하여 작은 원소가 앞으로 오도록 정렬하며 병합하는 과정을 나타낸다.

아래 그림은 병합정렬의 프로세스를 쉽게 나타낸다.

출처 - https://ko.wikipedia.org/wiki/%ED%95%A9%EB%B3%91_%EC%A0%95%EB%A0%AC

병합정렬 특징

주어진 배열 이외에 다른 추가 메모리를 요구한다. (추가적인 List가 필요하다)
중복된 값은 입력 순서와 동일하게 정렬되는 안정 정렬(Stable Sort)이다.
데이터들 간의 상대적 크기 관계만을 이용해서 정렬하는 비교 정렬이다.
분할 정복 알고리즘을 기반으로 정렬되는 방식으로, 퀵 정렬과는 다르게 항상 균등하게 List가 나뉜다.
일반적으로 퀵 정렬 보다 느리다.

시간복잡도

병합 정렬의 시간복잡도는 O(NlogN)의 시간복잡도를 갖는다.
Best : O(NlogN)
Avg : O(NlogN)
Worst : O(NlogN)

Code

#include <iostream>

using namespace std;

// 분할하는 리스트를 따로 설정하지않고 하나만 설정
int sorted[8];

// 합병 함수
void merge(int arr[], int start, int end) {
	int mid = (start + end) / 2;
	int i = start;
	int j = mid + 1;
	int k = start;

	//왼쪽 리스트와 오른쪽 리스트의 값을 비교(정렬)하면서 sorted란 배열에 합친다.
	while (i <= mid && j <= end) {
		if (arr[i] < arr[j]) {
			sorted[k++] = arr[i++];
		}
		else {
			sorted[k++] = arr[j++];
		}
	}
	if (i > mid) {
		while (j <= end) {
			sorted[k++] = arr[j++];
		}
	}
	if (j > end) {
		while (i <= mid) {
			sorted[k++] = arr[i++];
		}
	}


	for (int i = 0; i <= end; i++) {
		arr[i] = sorted[i];
		cout << arr[i] << ' ';
	}
	cout << '\n';

}

//주어진 정렬을 더 이상 나눌 수 없을 때 까지 쪼갠 후, 크기가 1인 배열들을 순차적으로 합치며 정렬한다.
void mergeSort(int arr[], int start, int end) {

	if (start < end) {
		int mid = (start + end) / 2;
		mergeSort(arr, start, mid);
		mergeSort(arr, mid + 1, end);
		merge(arr, start, end);
	}

}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int arr[9] = { 54, 26, 93, 17, 77, 31, 44, 55, 20 };

	mergeSort(arr, 0, 7);

}

티스토리

[Algorithm] C++ Merge Sort (병합정렬)

[Algorithm] C++ Merge Sort (병합정렬)

병합정렬

병합정렬 알고리즘

예시

병합정렬 특징

시간복잡도

관련 알고리즘 문제

Code