[C언어 소스] 병합 정렬(합병 정렬, Merge Sort) 알고리즘

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

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

알고리즘

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

점근식 계산

병합 정렬에서 분할 과정은 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)의 성능을 보여줍니다. 특히 언제나 반 씩 분할한 후에 정복하기 때문에 자료의 배치 상태에 관계없이 일정한 성능을 보여주는 정렬 방식입니다.

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

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

소스 코드

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

#include 
#include 
#include 

#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 
#include 
#include 

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