합병 정렬(Merge sort)이란?
- 합병정렬(merge sort)은 정렬 알고리즘의 한 종류로, 폰 노이만이 개발한 알고리즘이다.
- 이 정렬은 안정 정렬에 속하며, 분할 정복(divide and conquer) 알고리즘의 하나이다.
합병 정렬(Merge sort) 아이디어
합병(Merge)라는 이름에서 알 수 있듯, 합병 정렬의 기본 아이디어는 정렬할 배열을 분할하여, 작은 조각으로 나눈 후 더 이상 나눌 수 없을 때(하나의 원소만 있을때) 다른 조각과 비교하며 합쳐 정렬하는 알고리즘이다.
과정
- 정렬되지 않은 리스트를 2개의 리스트로 나눈다.
- 각 리스트의 길이가 1이 될때까지 반복한다(길이가 1인 리스트는 정렬된 것으로 간주한다.)
- 2개의 리스트의 값들을 처음부터 하나씩 비교하여 두 개의 리스트의 값 중에서 더 작은 값을 새로운 리스트로 옮긴다.
- 둘중 한 리스트가 끝날 때까지 이를 반복한다.
- 한 리스트가 끝나면, 나머지 값들은 새 리스트에 복사해서 넣어준다(이미 정렬되어 있으므로)
- 2번 과정을 하나의 리스트가 될때까지 반복한다
합병 정렬(Merge sort) 증명
Merge 과정은 문제없이 기능한다 가정
귀납적 증명(Proof by Induction)
1. Base Case (기본 단계):
배열의 크기가 1 또는 0인 경우
- 배열의 크기가 0 또는 1이면, 이미 정렬된 상태이다.
2. Inductive Hypothesis (귀납 가정):
배열의 크기가 n 이하인 모든 배열에 대해 Merge sort가 올바르게 작동한다고 가정.
3. Inductive Step (귀납적 단계):
배열의 크기가 n+1인 배열에 대해서 Merge sort가 올바르게 작동함을 증명.
- 크기가 n+1인 배열 A를 반으로 나누어 두 개의 하위 배열 L과 R로 나눈다고 가정하자. 각 하위 배열의 크기는 대략 n/2 또는 그와 비슷하다.
- 귀납 가정에 따라, 배열 L과 배열 R에 대해 각각 Merge sort를 호출하면, L과 R은 각각 오름차순으로 정렬된다.
- Merge 과정이 끝나면, L과 R의 모든 요소가 오름차순으로 정렬된 하나의 배열로 합쳐지고. 이 배열은 오름차순으로 정렬된 상태이다.
따라서 배열의 크기가 n+1일 때도 Merge sort는 올바르게 작동한다.
합병 정렬(Merge sort) 시간복잡도
$T(n)=2T(\frac{n}{2})+n$ (이때 n은 merge시 걸리는 시간)
$\ \ \ \ \ \ \ \ =2(2T(\frac{n}{4})+\frac{n}{2})+n=4T(\frac{n}{4})+2n$
$\ \ \ \ \ \ \ \ =4(2T(\frac{n}{8})+\frac{n}{4})+2n=8T(\frac{n}{8})+3n$
$\ \ \ \ \ \ \ \ ...$
$\ \ \ \ \ \ \ \ =nT(1)+log(n)*n$
$\ \ \ \ \ \ \ \ =n*log(n)$
합병 정렬(Merge sort) 구현
#include <iostream>
using namespace std;
// 두 개의 하위 배열을 병합하는 함수
void merge(int arr[], int left, int mid, int right) {
int n1 = mid - left + 1; // 왼쪽 하위 배열의 크기
int n2 = right - mid; // 오른쪽 하위 배열의 크기
// 임시 배열 생성
int L[n1], R[n2];
// 원본 배열의 값을 각각 왼쪽과 오른쪽 임시 배열로 복사
for (int i = 0; i < n1; i++)
L[i] = arr[left + i];
for (int j = 0; j < n2; j++)
R[j] = arr[mid + 1 + j];
// 두 배열을 병합하여 정렬된 상태로 원래 배열에 다시 삽입
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
// 왼쪽 배열의 남은 요소 복사
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
// 오른쪽 배열의 남은 요소 복사
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
// Merge Sort 알고리즘
void mergeSort(int arr[], int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
// 왼쪽과 오른쪽 배열에 대해 재귀적으로 정렬
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
// 정렬된 두 배열을 병합
merge(arr, left, mid, right);
}
}
// 배열을 출력하는 함수
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}
int main() {
int arr[] = {12, 11, 13, 5, 6, 7};
int arr_size = sizeof(arr) / sizeof(arr[0]);
cout << "Given array is \n";
printArray(arr, arr_size);
mergeSort(arr, 0, arr_size - 1);
cout << "\nSorted array is \n";
printArray(arr, arr_size);
return 0;
}'CS > Algorithm' 카테고리의 다른 글
| 프림 알고리즘(Prim Algorithm) 구현과 증명 (0) | 2024.09.17 |
|---|---|
| 그리디 알고리즘(Greedy Algorithm, 탐욕법) (0) | 2024.07.13 |
