병합 정렬(합병 정렬, Merge Sort) 알고리즘

1. 유튜브 동영상 강의

병합 정렬 알고리즘 동영상 강의

 

2. 알고리즘

이번에는 병합 정렬 알고리즘을 살펴봅시다.

병합 정렬 알고리즘은 배열을 작은 단위의 배열로 분할한 후에 분할한 배열을 정렬하고 이들을 다시 정렬하면서 전체 배열을 정렬하는 알고리즘입니다.

병합 정렬(base:배열의 시작 주소, n: 원소 개수, compare:비교 논리)
    ah:= n/2
    bh:= n – ah;
    조건(n이 1보다 작거나 같으면) 종료
    병합정렬(base,ah,compare)
    병합접열(base+ah,bh,compare)
    tbase에 동적 메모리 할당(원소크기*원소개수)
    메모리 복사(tbase,base)
    ai:=0
    bi:=ah
    i:=0
    반복(ai가 ah보다 작으면서 bi가 n보다 작다)
        조건(tbase[ai]가 tbase[bi]보다 작거나 같으면
            base[i] := base[ai]
            ai:= ai+1
        아니면
             base[i]:= base[bi]
             bi:= bi+1
        i:=i+1
    반복(ai가 ah보다 작다)
        base[i]:= tbase[ai]
        i:=i+1
        ai:=ai+1
    반복(bi가 n보다 작다)
        base[i]:= tbase[bi]
        i:=i+1
        bi:=bi+1

병합 정렬 실행 화면

3. 점근식 계산

병합 정렬에서 분할 과정은 n개일 때 1, n/2일 때 두 번(분할한 두 개가 각각 한 번 분할),…해서 총 n-1번 분할합니다.

분할 횟수 = 1+2+4+8+…+n/2 = n-1

정복 과정에서는 분할 횟수가 h이고 분할한 h개를 h/2개로 병합하기 위해 비교 회수는 최악일 때 n보다 작습니다. 분할 횟수는 logN이므로 정복에 들어가는 전체 비용은 NlogN보다 작습니다.

정복 과정에서의 비교 횟수<=NlogN

따라서 병합 정렬의 전체 비용은 최악일 때 O(NlogN)이라고 말할 수 있습니다. 앞에서 살펴본 힙 정렬과 마찬가지로 병합 정렬은 O(NlogN)의 성능을 보여줍니다. 특히 언제나 반 씩 분할한 후에 정복하기 때문에 자료의 배치 상태에 관계없이 일정한 성능을 보여주는 정렬 방식입니다.

그리고 같은 값을 갖고 있을 때 원래 앞에 있는 원소가 정렬 후에도 앞에 있게 정렬하는 안정적인 정렬 알고리즘입니다. 만약 정렬에서 우선적으로 정렬할 키와 차선으로 정렬할 키가 있을 때 차선의 키로 정렬한 후에 우선적인 키로 안정적인 정렬을 수행하면 원하는 결과를 얻을 수 있습니다.

두 개의 키로 정렬하기: 차선의 키로 정렬 → 우선적인 키로 안정적인 정렬

4. 소스 코드

//https://ehpub.co.kr
//[언제나 C언어] 병합 정렬(Merge Sort) [예제 Center]

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

#define SWAP(a,b) {int t; t=a; a=b; b=t;}

void MergeSort(int* base, int n);
void ViewArr(int* base, int n);
int main()
{
    int arr[10] = { 9,4,3,10,5,8,7,6,2,1 };
    ViewArr(arr, 10);
    MergeSort(arr, 10);
    ViewArr(arr, 10);
    return 0;
}
void MergeSort(int* base, int n)
{
    int ahalf = n / 2;
    int bhalf = n - ahalf;
    int ai = 0, bi = ahalf;
    int i = 0;
    int* tbase = 0;//static int tbase[100000];

    if (n <= 1)
    {
        return;
    }

    MergeSort(base, ahalf);
    MergeSort(base+ahalf, bhalf);

    tbase = (int*)malloc(sizeof(int) * n);
    memcpy(tbase, base, sizeof(int) * n);
    
    while ((ai < ahalf) && (bi < n))
    {
        if (tbase[ai] <= tbase[bi])
        {
            base[i] = tbase[ai];
            ai ++;
        }
        else
        {
            base[i] = tbase[bi];
            bi++;
        }
        i++;
    }
    while (ai < ahalf)
    {
        base[i] = tbase[ai];
        i++;
        ai++;
    }
    while (bi < n)
    {
        base[i] = tbase[bi];
        i++;
        bi++;
    }
    free(tbase);
}
void ViewArr(int* base, int n)
{
    int i = 0;
    for (i = 0; i < n; i++)
    {
        printf("%d ", base[i]);
    }
    printf("\n");
}

시뮬레이션 코드

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

#define SWAP(a,b)  {int t; t = a; a=b; b=t;}//a와 b를 교환

int* origin;
int on;

void MergeSort2(int* base, int n);
void MergeSort(int* base, int n);
void ViewArr(int* arr, int n);
int main(void)
{
    int arr[10] = { 9,4,3,10,5,8,7,6,2,1 };
    origin = arr;
    on = 10;    
    ViewArr(origin, on);    
    MergeSort2(arr, 10);
    getch();
    ViewArr(origin, on);
    system("pause");
    return 0;
}

void MergeSort(int* base, int n)
{
    int ahalf = n / 2; //배열의 앞쪽 개수
    int bhalf = n - ahalf; //배열의 뒤쪽 개수
    int ai = 0, bi = ahalf;
    int i = 0;

    int* tbase = 0;

    if (n <= 1)//배열의 크기가 1보다 작거나 같을 때
    {
        return;
    }


    MergeSort(base, ahalf);//앞쪽 배열 재귀호출로 정렬
    MergeSort(base + ahalf, bhalf);//뒤쪽 배열 재귀호출로 정렬
    
    tbase = (int*)malloc(sizeof(int) * n);//배열 크기의 임시 공간을 할당
    memcpy(tbase, base, sizeof(int) * n);//임시 공간에 배열 메모리 복사

    while ((ai < ahalf) && (bi < n))
    {
        if (tbase[ai] <= tbase[bi])//뒤쪽이 크거나 같을 때
        {
            base[i] = tbase[ai];//앞쪽 배열의 원소를 대입
            ai++;
        }
        else
        {
            base[i] = tbase[bi];//뒤쪽 배열의 원소를 대입
            bi++;
        }
        i++;
    }


    while (ai < ahalf)//앞쪽 배열의 남은 것들을 대입
    {
        base[i] = tbase[ai];
        i++;
        ai++;
    }

    while (bi < n)//뒤쪽 배열의 남은 것들을 대입
    {
        base[i] = tbase[bi];
        i++;
        bi++;
    }

    free(tbase);//임시 버퍼에 할당한 메모리 해제        
}

void PrintSpace(int n);
void MergeSort2(int* base, int n)
{
    int ahalf = n / 2; //배열의 앞쪽 개수
    int bhalf = n - ahalf; //배열의 뒤쪽 개수
    int ai = 0, bi = ahalf;
    int i = 0;

    int* tbase = 0;

    if (n <= 1)//배열의 크기가 1보다 작거나 같을 때
    {
        return;
    }

    
    MergeSort2(base, ahalf);//앞쪽 배열 재귀호출로 정렬
    PrintSpace(base - origin);
    ViewArr(base, ahalf);
    
    MergeSort2(base + ahalf, bhalf);//뒤쪽 배열 재귀호출로 정렬
    PrintSpace(base + ahalf - origin);
    ViewArr(base + ahalf, bhalf);
    
    tbase = (int*)malloc(sizeof(int) * n);//배열 크기의 임시 공간을 할당
    memcpy(tbase, base, sizeof(int) * n);//임시 공간에 배열 메모리 복사

    while ((ai < ahalf) && (bi < n))
    {
        if (tbase[ai] <= tbase[bi])//뒤쪽이 크거나 같을 때
        {
            base[i] = tbase[ai];//앞쪽 배열의 원소를 대입
            ai++;
        }
        else
        {
            base[i] = tbase[bi];//뒤쪽 배열의 원소를 대입
            bi++;
        }
        i++;
    }


    while (ai < ahalf)//앞쪽 배열의 남은 것들을 대입
    {
        base[i] = tbase[ai];
        i++;
        ai++;
    }

    while (bi < n)//뒤쪽 배열의 남은 것들을 대입
    {
        base[i] = tbase[bi];
        i++;
        bi++;

    }

    free(tbase);//임시 버퍼에 할당한 메모리 해제        
    
}
void PrintSpace(int n)
{
    int i = 0;
    getch();
    for (i = 0; i < n; i++)
    {
        printf("   ");
    }
}
void ViewArr(int* arr, int n)
{
    int i = 0;
    for (i = 0; i < n; i++)
    {
        printf("%2d ", arr[i]);
    }
    printf("\n");
}