6.2 병합 정렬 알고리즘 구현

6.2 병합 정렬 알고리즘 구현

---

 이제 병합 정렬 알고리즘을 구체적으로 구현합시다.

#include "common.h"

#include "Book.h"

typedef void *Element;

typedef int (*Compare)(Element , Element);

 

void merge_sort(Element *base, int n, Compare compare)

{

 n의 절반의 크기를 ahalf에 기억합니다. 이는 배열을 분할할 때 앞쪽 배열의 원소 개수입니다.

    int ahalf = n/2;

 배열을 분할할 때 뒤쪽 배열의 원소 개수를 bhalf에 기억합니다.

    int bhalf = n - ahalf;

 분할할 배열을 하나의 배열로 정복하기 위한 인덱스를 선언합니다. ai는 앞쪽 배열의 인덱스로 사용할 것이므로 0으로 초기화합니다. bi는 뒤쪽 배열의 인덱스로 사용할 것이므로 ahalf로 초기화합니다. 그리고 정렬 상태의 배열을 만들어가는 과정에서의 인덱스로 사용할 i를 0으로 초기화합니다.

    int ai=0, bi=ahalf;

    int i=0;

 병합 정렬은 원본 배열의 크기만큼의 메모리를 할당하여 이를 이용하므로 변수를 선언합시다.

    Element *tbase=0;

 

 만약 원소의 개수가 1보다 작거나 같다면 분할할 필요가 없고 정렬할 필요가 없으므로 함수를 종료합니다.

    if(n<=1)

    {

        return;

    }

 

 재귀 호출로 앞쪽 배열을 정렬합니다.

    merge_sort(base, ahalf, compare);

 재귀 호출로 뒤쪽 배열을 정렬합니다.

    merge_sort(base+ahalf, bhalf, compare);

 이제 정렬할 앞쪽 배열과 뒤쪽 배열을 하나의 배열로 정복해야 합니다. tbase에 메모리를 할당하고 원본 배열의 내용을 복사합니다.

    tbase = (Element *)malloc(sizeof(Element)*n);

    memcpy(tbase,base,sizeof(Element)*n);

 

 ai가 ahalf(앞쪽 배열의 원소 개수)보다 작거나 bi가 n(배열의 원소 개수)보다 작으면 반복합니다.

    while((ai<ahalf)&&(bi<n))

    {

 복사한 tbase의 ai인덱스에 있는 원소가 bi인덱스에 있는 원소보다 작거나 같다면 base[i]에 ai인덱스에 있는 원소를 대입하고 ai를 1 증가합니다.

        if(compare(tbase[ai],tbase[bi])<=0)

        {

            base[i] = tbase[ai];

            ai++;

        }

 그렇지 않다면 base[i]에 bi인덱스에 있는 원소를 대입하고 bi를 1 증가합니다.

        else

        {

            base[i] = tbase[bi];

            bi++;

        }

 i도 1 증가합니다.

        i++;

    }

 반복문을 빠져 나왔을 때 ai가 ahalf보다 작다면 bi가 n에 도달한 것이므로 ai인덱스에서 ahalf 사이에 있는 원소들을 base 배열에 순차적으로 대입합니다.

    while(ai<ahalf)

    {

        base[i] = tbase[ai];

        i++;

        ai++;

    }

 마찬가지로 bi가 n보다 작다면 ai가 ahalf에 도달한 것이므로 bi인덱스에서 n사이에 있는 원소들을  base 배열에 순차적으로 대입합니다.

    while(bi<n)

    {

        base[i] = tbase[bi];

        i++;

        bi++;

    }

 임시로 사용한 tbase에 할당한 메모리를 해제합니다.

    free(tbase);

}

 테스트 코드는 다른 정렬 알고리즘과 차이가 없으므로 생략할게요.