합병정렬/병합정렬 (Merge Sort)
: 분할 정복 알고리즘
: 비교 정렬
: 안정 정렬
: 시간 복잡도는 O(n log2 n)
분할 정복 알고리즘(Divide and conquer algorithm)
그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법이나 알고리즘
1. 리스트의 길이가 1 이하이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는
2. 분할(divide): 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
3. 정복(conquer): 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
4. 결합(combine): 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다. 이때 정렬 결과가 임시배열에 저장된다.
5. 복사(copy): 임시 배열에 저장된 결과를 원래 배열에 복사한다.
위키피디아에서 가져온 알고리즘
7 5 3 1 4 9 8 6 2
총 9개의 숫자가 있다고 해보자
7 5 3 1 4 | 9 8 6 2
나눈다 (분할한다)
7 5 3 | 1 4 | 9 8 | 6 2
나눈다 (분할한다)
7 5 | 3 | 1 | 4 | 9 | 8 | 6 | 2
나눈다 (분할한다)
7 | 5 | 3 | 1 | 4 | 9 | 8 | 6 | 2
분할 완료
5 7 | 3 | 1 | 4 | 9 | 8 | 6 | 2
합친다 (합병한다)
3 5 7 | 1 4 | 8 9 | 2 6
합친다 (합병한다)
1 3 4 5 7 | 2 6 8 9
합친다 (합병한다)
1 2 3 4 5 6 7 8 9
합병 완료 (정렬 완료)
비교 정렬
원소들을 정렬할 때 원소들의 순서에만 의존하는 알고리즘
비교 정렬이 아닌 것은 counting sort, radix sort 같은 것
안정 정렬(stable)
동일한 두 원소는 이미 위치가 정해져있어서 바뀌지 않음
왼쪽이 오른쪽보다 클 경우에만 바뀌기 때문에 (같은 경우는 바뀌지 않음)
시간 복잡도는 O(n log2 n)
요소의 개수가 2의 거듭제곱이라고 가정했을 때,
순환호출의 깊이 k = (log2 n)
하나의 합병 단계에서는 최대 n번의 비교연산이 필요
따라서 총 비교연산은 최대 (n log2 n)번
임시 배열이 필요하다
부분 배열들의 숫자를 임시 배열에 정렬한 상태로
이것을 다시 원래의 배열에 복사
#include <stdio.h>
void merge(int *arr, int left, int right)
{
int mid;
int temp[1000001];
int l, m, t;
mid = (left + right) / 2;
l = left;
m = mid + 1;
t = left;
//정렬 후 합병
while (l <= mid && m <= right)
{
if (arr[l] <= arr[m])
temp[t++] = arr[l++];
else
temp[t++] = arr[m++];
}
if (l > mid)
{
while(m <= right)
{
temp[t++] = arr[m++];
}
}
else
{
while(l <= mid)
{
temp[t++] = arr[l++];
}
}
//원래 배열로 복사
while (left <= right)
{
arr[left] = temp[left];
left++;
}
}
void merge_sort(int *arr, int left, int right)
{
int mid;
if (left >= right)
return ;
mid = (left + right) / 2;
merge_sort(arr, left, mid);
merge_sort(arr, mid + 1, right);
merge(arr, left, right);
}
#include <iostream>
using namespace std;
int temp[1000000];
int *arr;
void merge(int left, int mid, int right)
{
int l, m, t;
l = left;
m = mid + 1;
t = left;
//정렬 후 합병
while (l <= mid && m <= right)
{
if (arr[l] <= arr[m])
temp[t++] = arr[l++];
else
temp[t++] = arr[m++];
}
if (l > mid)
{
while(m <= right)
temp[t++] = arr[m++];
}
else
{
while(l <= mid)
temp[t++] = arr[l++];
}
//원래 배열로 복사
while (left <= right)
{
arr[left] = temp[left];
left++;
}
}
void merge_sort(int left, int right)
{
int mid;
if (left >= right)
return ;
mid = (left + right) / 2;
merge_sort(left, mid);
merge_sort(mid + 1, right);
merge(left, mid ,right);
}
디버거 돌리면 세그폴트나거나(배열 초기화 안하면) 백준 답이 틀렸거나(전역변수로 배열을 선언하거나) 시간초과나거나(그 외 모두)..
https://www.acmicpc.net/board/view/81856
arr 배열의 크기가 너무 커서 생긴 에러 같습니다.
arr을 전역변수로 선언하여 제출하면 런타임에러가 발생되지 않지만 틀렸습니다를 받게 됩니다.
뭐가 문제인지 모르겠다
,,
C++로 다시 풀면서 수정함
코드상 오류는 더이상 없는데
이제는 메모리 초과가 뜸
퀵소트 갑니다..
https://ko.wikipedia.org/wiki/%ED%95%A9%EB%B3%91_%EC%A0%95%EB%A0%AC
https://taaewoo.tistory.com/5
https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html
C언어로 쉽게 풀어쓴 자료구조