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

Sadie·2022년 7월 18일
0

합병정렬/병합정렬 (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)번

  • 임시 배열이 필요하다
    부분 배열들의 숫자를 임시 배열에 정렬한 상태로
    이것을 다시 원래의 배열에 복사



소스코드 (C)

#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);
}

소스코드 (C++)

#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);
}


백준 2751

디버거 돌리면 세그폴트나거나(배열 초기화 안하면) 백준 답이 틀렸거나(전역변수로 배열을 선언하거나) 시간초과나거나(그 외 모두)..

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언어로 쉽게 풀어쓴 자료구조

0개의 댓글