9.1.3 힙 정렬 알고리즘 구현

이번에는 힙 정렬 알고리즘을 구현해 보기로 해요.

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

초기 힙 구성

루트와 맨 마지막 자손 교환

    n을 1 감소

반복(n: n->1)

힙 구성

루트와 맨 마지막 자손 교환

        n을 1 감소

초기 힙 구성(base:배열의 시작 주소, n: 원소 개수, compare:비교 논리)

반복(i:1->n)

        j:=1

반복(j>0)

            pa:=PARENT(j)

조건: compare(base[j], base[pa])이 0보다 크면

                base[j], base[pa] 교환

                j: = pa

아니면

내부 루프 탈출

힙 구성(base:배열의 시작 주소, n: 원소 개수, compare:비교 논리)

반복

    lc:= LCHILD(me)

    rc:= RCHILD(me)

자식이 없으면

탈출

조건 왼쪽 자식만 있을 때

조건 compare(base[me],base[lc])>0일 때

        base[me], base[lc] 교환

탈출

    bc := 왼쪽 자식과 오른쪽 자식 중에 자료가 큰 값의 인덱스

조건 compare(base[bc],base[me])>0일 때

        base[bc],base[me] 교환

아니면

탈출

참고로 2.1.2에서 공통으로 사용할 코드를 이용하세요.

먼저 인덱스를 계산하는 매크로 상수를 정의하세요.

#define LCHILD(me)   (2*me +1)
#define RCHILD(me)  (LCHILD(me)+1)
#define PARENT(me)  ((me-1)/2)

먼저 초기 힙을 구성해야 합니다. 초기 힙은 인덱스 1에서 마지막까지 순차적으로 초기 힙을 구성합니다.

template <typename data, typename compare>
void heap_sort(data *base, size_t n, compare algo)
{
    for( size_t i =1 ; i<n; i++)
    {

힙 구성에 참가할 자료는 부모와 비교하면서 교환이 반복할 수 있습니다. 그리고 그 과정에서 인덱스 값이 변할 수 있으므로 별도의 변수에 설정하여 사용하세요.

        int j=i;

힙 구성에 참가할 자료를 부모와 비교하면서 교환을 반복할 때 루트까지 오면 더 이상 비교하지 않습니다.

        while(j>0)//루트가 아니면 반복
        {

먼저 자신의 부모 인덱스를 구하세요.

            int pa = PARENT(j);//부모 인덱스를 구하기

만약 부모의 자료보다 더 크면 부모와 자료를 교환하고 인덱스를 부모의 인덱스로 변경합니다.

            if( algo(base[j], base[pa]) >0 ) //부모보다 크면
            {
                swap(base[j],base[pa]);//부모와 교환
                j = pa;
            }

만약 부모의 자료보다 크지 않다면 힙을 구성한 것이므로 반복문을 탈출합니다.

            else
            {
                break;
            }            
        }
    }

초기 힙 구성이 끝나면 루트와 마지막 자손의 자료를 교환하고 정렬할 범위를 1줄입니다.

    swap(base[0],base[n-1]);//루트와 마지막 자손 교환
    n--;
    size_t me;
    size_t lc;
    size_t rc;

이후에 힙 구성은 정렬할 범위가 1이 되기 전까지 반복합니다.

    while(n>1)//반복: n이 1보다 크면 
    {

원래 마지막 자손이었지만 루트의 자료와 교환하여 현재 루트인 자료가 있어야 할 위치를 찾아야 합니다. 따라서 현재 자신의 인덱스를 0으로 설정하세요.

        me = 0;

자신의 위치를 찾을 때까지 반복합니다.

        while(1)
        {

자신의 왼쪽 자식과 오른쪽 자식의 인덱스를 구하세요.

            lc = LCHILD(me);
            rc = RCHILD(me);

만약 왼쪽 자식의 인덱스가 n보다 크거나 같으면 자식이 없는 것이므로 반복문을 탈출하세요.

            if(lc>=n)//자식이 없음
            {
                break;
            }

만약 rc가 n이면 왼쪽 자식만 있다는 것입니다.

            if(rc == n)//왼쪽 자식만 있음
            {

왼쪽 자식이 자신보다 더 크면 자료를 교환하세요.

                if(algo(base[me], base[lc])<0)
                {
                    swap(base[me],base[lc]);
                }

자신의 왼쪽 자식만 있었으므로 교환한 위치의 자식은 없으니 반복문을 탈출하세요.

                break;
            }

둘 다 있을 때는 왼쪽 자식과 오른쪽 자식 중에 큰 자식의 인덱스를 먼저 구하세요.

            int bc = lc;
            if(algo(base[lc], base[rc])<0)
            {
                bc = rc;
            }

자신과 비교하여 자식이 크면 자료를 교환하고 자식의 인덱스로 변경하세요.

            if(algo(base[bc],base[me])>0)
            {
                swap(base[bc],base[me]);
                me = bc;
            }

만약 자식이 더 크지 않다면 힙을 구성한 것이므로 반복문을 탈출하세요.

            else
            {
                break;
            }
        }

힙 구성이 끝나면 루트와 마지막 자손의 자료를 교환한 후에 정렬 범위를 1 줄입니다.

        swap(base[0],base[n-1]);//루트와 마지막 자손 교환
        n--;
    }        
}

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

#define MAX_DATA 1000

int main()
{
    Member *base[MAX_DATA];
    //퀵 정렬이 잘 동작하는지 
    //10개 원소를 번호 순으로 정렬하여 
    //확인하고 이름 순으로 정렬하여 확인하세요.
    MakeRandomMembers(base,10);
    cout<<"정렬 전"<<endl;
    ViewMembers(base,10);
    quick_sort(base,10,CompareByNum);
    cout<<"번호로 정렬 후"<<endl;
    ViewMembers(base,10);
    quick_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();    
    quick_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);
    quick_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
수행 속도:132
수행 성능 테스트2 자료 개수:100
수행 속도:9