9.4 병합 정렬(Merge Sort) [디딤돌 자료구조와 알고리즘 with C++]

9.4 병합 정렬(Merge Sort)

이제 병합 정렬 알고리즘을 살펴보기로 해요.

 

병합 정렬은 배열을 분할한 후에 분할한 배열끼리 정렬하는 것을 반복하여 전체를 정렬하는 알고리즘입니다. 이처럼 커다란 문제를 작은 문제로 분할하고 분할한 작은 영역의 문제를 해결하면서 커다란 문제를 해결하는 알고리즘을 분할 정복(Divide And Conquer) 알고리즘이라고 말합니다.

 

먼저 분할하는 과정이 필요합니다. 분할하다가 원소의 개수가 1보다 작거나 같으면 분할은 끝납니다.

조건(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와 같거나 bi가 n과 같으면 한 쪽 배열의 나머지 원소를 임시 버퍼에 옮깁니다.

    반복(ai<h)

        tbase[ci]:=base[ai]

        ai++, ci++

    반복(bi<n)

        tbase[ci]:=base[bi]

        ci++, bi++

마지막으로 임시 버퍼의 내용으로 원래 배열에 복사한 후에 임시 버퍼의 메모리를 해제합니다.

    base에 tbase 내용 복사

    tbase 메모리 해제

 

다음은 병합 정렬 알고리즘의 의사 코드입니다.

병합 정렬(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 메모리 해제

 

 

9.4.1 병합 정렬 알고리즘 성능 분석

병합 정렬 알고리즘 성능을 분석합시다.

병합 정렬(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 메모리 해제

 

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

 

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

 

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

 

 

 

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))

    {

        if(algo(base[ai], base[bi])>0)

        {

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

            tbase[ci] = base[bi];

            bi++;

        }

        else

        {

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

            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