9.4.2 병합 정렬 알고리즘 구현

병합 정렬 알고리즘을 구현합시다.

병합 정렬(base:배열의 시작 주소, n: 원소 개수, compare:비교 논리)

조건(n<=1) 종료

    h:=n/2

병합 정렬(base, h, compare)

병합 정렬(base+h, n- h, compare)

    ai:=0    bi:=h    ci:=0

    tbase에 크기 n인 버퍼 할당

반복(ai<h 이면서 bi<n)

조건(compare(base[ai],base[bi])>0)

            tbase[ci] := base[bi]    bi++

아니면

            tbase[ci]:= base[ai]    ai++

        ci++

반복(ai<h)

        tbase[ci]:=base[ai]    ai++, ci++

반복(bi<n)

        tbase[ci]:=base[bi]    ci++, bi++

    base에 tbase 내용 복사

    tbase 메모리 해제

template <typename data, typename compare>
void merge_sort(data *base, size_t n, compare algo)
{

분할 과정에서 n이 1보다 작거나 같으면 종료합니다.

    if(n<=1)
    {
        return;
    }

앞 쪽 요소와 뒤 쪽 요소로 분할합니다.

    size_t h = n/2;
    size_t lh = n-h;
    merge_sort(base,h,algo);//분할
    merge_sort(base+h, lh, algo);//분할

이제 정복 과정입니다. 정복 과정에 사용할 인덱스를 설정하세요.

    //이 후의 분할한 배열의 내용을 목적에 맞게 정복한다.
    size_t ai = 0;
    size_t bi = h;
    size_t ci = 0;

임시 버퍼를 할당합니다.

    data *tbase = new data[n];

앞 쪽 배열의 요소를 순차 탐색할 ai가 h보다 작으면서 뒤 쪽 배열의 요소를 순차 탐색할 bi가 n보다 작으면 반복합니다.

    while((ai<h)&&(bi<n))
    {

앞 쪽 요소가 크면 뒤 쪽 요소를 임시 버퍼에 배치하고 bi를 다음 위치로 이동합니다.

        if(algo(base[ai], base[bi])>0)
        {
            tbase[ci] = base[bi];
            bi++;
        }

그렇지 않으면 앞 쪽 요소를 임시 버퍼에 배치하고 ai를 다음 위치로 이동합니다.

        else
        {
            tbase[ci] = base[ai];
            ai++;
        }

언제나 ci는 다음 위치로 이동합니다.

        ci++;
    }

만약 ai가 h보다 작다면 아직 앞 쪽 요소 중에 임시 버퍼로 배치하지 않은 것들이 있으니 배치하세요.

    while(ai<h)
    {
        tbase[ci] = base[ai];
        ai++;
        ci++;
    }

bi가 n보다 작다면 아직 뒤 쪽 요소 중에 임시 버퍼로 배치하지 않은 것들이 있으니 배치하세요.

    while(bi<n)
    {
        tbase[ci] = base[bi];
        bi++;
        ci++;
    }

마지막으로 임시 버퍼의 내용을 원본 배열에 복사한 후에 임시 버퍼를 소멸하세요.

    for(ci=0; ci<n;ci++)
    {
        base[ci] = tbase[ci];
    }
    delete[] tbase;
}

테스트 코드도 2.1.3에서 작성한 코드에서 sequential_sort 부분을 merge_sort로 변경하세요.

#define MAX_DATA 1000

int main()
{
    Member *base[MAX_DATA];
    //병합 정렬이 잘 동작하는지 
    //10개 원소를 번호 순으로 정렬하여 
    //확인하고 이름 순으로 정렬하여 확인하세요.
    MakeRandomMembers(base,10);
    cout<<"정렬 전"<<endl;
    ViewMembers(base,10);
    merge_sort(base,10,CompareByNum);
    cout<<"번호로 정렬 후"<<endl;
    ViewMembers(base,10);
    merge_sort(base,10,CompareByName);
    cout<<"이름으로 정렬 후"<<endl;
    ViewMembers(base,10);
    RemoveMembers(base,10);

    //그리고 MAX_DATA 개일 때 수행 속도와 
    //MAX_DATA/10 개일 때 수행 속도를 비교해 보세요.
    clock_t st,et;
    MakeRandomMembers(base,MAX_DATA);
    cout<<"수행 성능 테스트1 자료 개수:"<<MAX_DATA<<endl;
    st = clock();
    merge_sort(base,MAX_DATA,CompareByName);
    et=clock();
    cout<<"수행 속도:"<<et-st<<endl;
    RemoveMembers(base,MAX_DATA);

    MakeRandomMembers(base,MAX_DATA/10);
    cout<<"수행 성능 테스트2 자료 개수:"<<MAX_DATA/10<<endl;
    st = clock();
    MakeRandomMembers(base,MAX_DATA/10);
    merge_sort(base,MAX_DATA/10,CompareByName);
    et=clock();
    cout<<"수행 속도:"<<et-st<<endl;
    RemoveMembers(base,MAX_DATA/10);
    return 0;
}

▷ 실행 결과

정렬 전
0000757147,이름0167851000
0301413356,이름0336971124
0659598368,이름0160567225
0391749387,이름0004890851
0035766290,이름0026239572
0473038164,이름0000597006
0003615544,이름0326051436
0392289610,이름0118341522
0170427798,이름0037215528
0675016433,이름0168544290
번호로 정렬 후
0000757147,이름0167851000
0003615544,이름0326051436
0035766290,이름0026239572
0170427798,이름0037215528
0301413356,이름0336971124
0391749387,이름0004890851
0392289610,이름0118341522
0473038164,이름0000597006
0659598368,이름0160567225
0675016433,이름0168544290
이름으로 정렬 후
0473038164,이름0000597006
0391749387,이름0004890851
0035766290,이름0026239572
0170427798,이름0037215528
0392289610,이름0118341522
0659598368,이름0160567225
0000757147,이름0167851000
0675016433,이름0168544290
0003615544,이름0326051436
0301413356,이름0336971124
수행 성능 테스트1 자료 개수:1000
수행 속도:98
수행 성능 테스트2 자료 개수:100
수행 속도:7