병합 정렬
: 대표적인 분할 정복 방법을 채택한 알고리즘으로 O(NlogN)의 시간 복잡도를 가지는 정렬 알고리즘
특징
-. 일단 반으로 정확히 나누고 나중에 합치는 방식으로, 퀵 정렬(Quick Sort)와 다르게 Pivot 값이 존재하지 않는다.
-. 기존 데이터를 담을 추가적인 배열이 필요하다는 점에서 메모리 활용은 비효율적이다.
-. 초기 단계에는 모두 원소가 1인 상태로 분할되어있으며, 한 번 병합할 때마다 2의 배수만큼 씩 병합한다.
-. 너비는 N이지만 높이는 logN이기 때문에 전체 시간 복잡도는 NlogN이다.
너비? 높이?
너비: i와 j를 비교해 더 작은 값을 k 위치에 저장
N번의 시도 후 정렬 완료

높이: 너비 정렬을 총 logN 번 반복하면 정렬 완료
병합 정렬(Merge Sort) Sequence
코드
#include <iostream>
using namespace std;
#define number 8
int sorted[8]; // 정렬된 배열. 반드시 전역 변수로 선언.
void merge(int a[], int m, int middle, int n){
// m: 정렬할 배열의 시작 지점
// middle: 정렬할 배열의 중간 지점
// n: 정렬할 배열의 끝 지점
int i = m;
int j = middle+1;
int k = m;
// 작은 순서대로 배열에 삽입
while(i<=middle && j <= n){
// i가 j보다 더 작으면 새로운 배열에 저장
if(a[i] <= a[j]){
sorted[k] = a[i];
i++;
}
// 그렇지 않으면 j 값 저장
else{
sorted[k] = a[j];
j++;
}
k++; // 한 번 저장하면 k 증가
}
// 남은 데이터 삽입
// i가 먼저 끝났다면 j 모두 새로운 배열에 저장
if(i > middle){
for(int t = j; t <= n; t++){
sorted[k] = a[t];
k++;
}
}
// j가 먼저 끝났으면 i 모두 새로운 배열에 저장
else{
for(int t = i;t<=middle;t++){
sorted[k] = a[t];
k++;
}
}
// 정렬된 배열을 실제 배열에 삽입
for(int t = m; t <= n; t++){
a[t] = sorted[t];
}
}
void merge_sort(int a[], int m, int n){
// 크기가 1보다 큰 경우 return
if(m < n){
int middle = (m+n) / 2;
merge_sort(a, m, middle); // middle을 기준으로 왼쪽 병합정렬
merge_sort(a, middle+1, n); // middle을 기준으로 오른쪽 병합정렬
merge(a, m, middle, n); // 정렬 후 합치기
}
}
int main(void){
int arr[number] = {7, 6, 5, 8, 3, 5, 9, 1};
merge_sort(arr, 0, number-1);
for(int i=0;i<number;i++)
cout << arr[i] << " ";
cout << endl;
return 0;
}
출력
1 3 5 5 6 7 8 9
시간 복잡도
병합정렬은 정확히 반씩 나눈다는 점에서 최악의 경우에도 NlogN을 보장한다.
☞ 퀵 정렬이 가지는 한계(Pivot 값에 따라 편향되게 분할할 가능성이 있다는 점에서 최악의 경우 O(N^2)의 시간 복잡도를 가짐)를 보완할 수 있음.
'Algorithm' 카테고리의 다른 글
[Algorithm] 힙 정렬(Heap Sort) (0) | 2023.04.09 |
---|---|
[Algorithm] C++ STL sort 함수 (0) | 2023.04.08 |
[Algorithm] 기초 정렬 문제 (0) | 2023.04.08 |
[Algorithm] 퀵 정렬(Quick Sort) (0) | 2023.04.08 |
[Algorithm] 삽입 정렬(Insertion Sort) (0) | 2023.04.03 |