9.1 힙 정렬 알고리즘 [디딤돌 자료구조와 알고리즘 with C++]

9.1 힙 정렬 알고리즘

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

 

힙 정렬은 완전 이진 트리의 한 종류인 힙 트리를 이용하여 정렬하는 알고리즘입니다. 먼저 힙 트리가 무엇인지 살펴본 후에 힙 정렬 알고리즘을 알아보고 분석 및 구현해 봅시다.

 

힙 트리는 부모의 값이 자식의 값보다 큰 값을 보장하는 최대 힙과 작은 값을 보장하는 최소 힙이 있습니다. 최대 힙으로 표현한 힙 트리의 루트에는 가장 큰 값을 갖고 최소 힙으로 표현하면 가장 작은 값을 갖습니다.

 

힙 트리처럼 완전 이진 트리는 배열로 많이 표현합니다. 완전 이진 트리가 아닌 이진 트리도 배열로 표현할 수 있지만 트리의 높이가 높아지고 한 쪽으로 기울어질 수록 비어있는 공간이 많아져서 메모리 효율이 떨어집니다. 하지만 완전 이진 트리는 마지막 자료가 있는 공간까지 모두 사용하여 빈 공간이 생기지 않습니다.

 

배열로 이진 트리를 표현할 때는 인덱스 0은 루트, 1은 루트의 왼쪽 자식, 2는 루트의 오른쪽 자식처럼 완전 이진 트리에서 노드를 매다는 순서와 배열의 인덱스가 같습니다. 완전 이진 트리에 자료를 매달때 배열로 표현하면 보관한 마지막 자료 뒤에 보관합니다. 하지만 완전 이진 트리가 아니면 계산에 의해 매달 위치를 찾아야 하며 비어있는 곳이 생깁니다.

 

매달 위치를 계산하는 것은 어렵지 않지만 비어있는 곳이 생기는 것은 이진 트리의 기울어짐이 커질 수록 비어있는 곳은 기하급수적으로 늘어날 수가 있어서 메모리 낭비가 심해질 수 있습니다. 이러한 이유로 완전 이진 트리가 아닐 때는 노드를 이용하여 구현하는 것이 효과적입니다. 반면 완전 이진 트리는 배열로 표현해도 메모리 낭비가 없기 때문에 노드를 이용하여 구현하지 않고 배열로 표현할 때가 많습니다.

 

완전 이진 트리를 표현하다보면 목적에 따라 부모나 자식의 위치를 알아야 할 때가 있습니다. 노드로 표현한다면 링크로 부모나 자식의 위치를 알 수 있지만 배열로 표현할 때는 계산에 의해 알아내야 합니다.

 

나의 인덱스가 me 일 때 왼쪽 자식의 인덱스는 2me+1 위치에 있습니다. 루트 노드의 인덱스가 0이고 왼쪽 자식의 인덱스는 1입니다. 그리고 인덱스 1인 노드의 자식 노드는 2X1+1 = 3 이므로 인덱스 3입니다. 위 그림을 보면 루트 노드의 왼쪽 자식 노드는 갖고 있는 자료 값이 20입니다. 아래 그림을 보면 자료 20은 인덱스 1에 보관함을 알 수 있습니다.

 

나의 왼쪽 자식의 인덱스가 lchild일 때 오른쪽 자식의 인덱스는 lchild + 1 입니다. 루트 노드의 인덱스가 0이고 왼쪽 자식의 인덱스가 1이므로 오른쪽 자식의 인덱스는 2입니다. 위 그림을 보면 루트 노드의 오른쪽 자식 노드는 갖고 있는 자료 값이 45입니다. 아래 그림을 보면 자료 45는 인덱스 2에 있습니다.

 

이를 정리하면 위 그림의 오른쪽 표처럼 나의 인덱스 값에 따라 왼쪽 자식, 오른쪽 자식, 부모의 인덱스를 알 수 있습니다.

 

이에 관한 식은 다음과 같습니다.

lchild = 2me +1

rchild = lchid +1

parent = (me-1)/2

 

매크로 함수로 표현하면 다음처럼 표현할 수 있겠죠.

#define LCHILD(me)   (2*me +1)

#define RCHILD(me)  (LCHILD(me)+1)

#define PARENT(me)  ((me-1)/2)

 

 

 

 

9.1.1 힙 정렬 알고리즘

힙 정렬은 힙 트리를 이용하는 알고리즘입니다. 최대 힙을 사용하면 크기 순(Ascend)으로 정렬하고 최소 힙을 사용하면 크기 역순(Descend)으로 정렬합니다.

 

힙 정렬은 먼저 힙 트리를 구성합니다. 그리고 루트의 값과 맨 마지막 값을 교환한 후에 정렬 범위를 1 줄입니다. 이와 같은 작업을 반복하여 정렬 범위가 1일 때까지 반복합니다.

 

최대 힙 트리에서 루트는 최대 값을 갖습니다. 따라서 마지막 값과 교환하면 제일 큰 값이 맨 뒤로 배치할 수 있습니다. 그리고 난 후에 정렬 범위를 줄여나가면 최종적으로 정렬 상태를 만들 수 있는 것입니다.

 

힙 정렬(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

            아니면

                내부 루프 탈출

 

 

 

루트와 마지막 자손 노드의 자료를 교환한 후에 노드 개수를 1 감소한 후에 루트에 있는 자료를 배치하는 것은 자식들 값 중에 큰 값과 비교하여 자신의 값이 작을 때 교환해 나가는 것을 반복합니다. 만약 자식이 없거나 자신이 자식들 값보다 크거나 같으면 작업은 끝납니다. 자식이 없거나 자식이 왼쪽만 있을 수 있으며 이를 고려한 의사 코드는 다음과 같습니다.

힙 구성(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] 교환

    아니면

        탈출

 

9.1.2 힙 정렬 알고리즘 성능 분석

이번에는 힙 정렬 알고리즘의 수행 속도를 계산해 보기로 해요.

 

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

    초기 힙 구성

    루트와 맨 마지막 자손 교환

    n을 1 감소

    반복(n: n->1)

        힙 구성

        루트와 맨 마지막 자손 교환

        n을 1 감소

 

힙 정렬 알고리즘 수행 속도는 초기 힙 구성과 힙 구성을 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

            아니면

                내부 루프 탈출

 

먼저 초기 힙 구성하는 시간을 계산해 보기로 해요.

 

초기 힙 구성은 내부 반복문을 n번 수행합니다. 그리고 내부 반복문은 트리 높이에 따라 비용이 차이가 생기는데 맨 마지막 자료를 구성할 때 걸리는 시간이 최악입니다. 그리고 맨 마지막 자료를 구성할 때 부모와 비교하면서 교환하기 때문에 최악일 때 비교와 교환을 트리의 높이만큼 진행합니다. 따라서 logN보다 작습니다. 따라서 초기 힙 구성 비용은 최악일 때도 NlogN보다 작습니다.

 

초기 힙 구성 비용 ≤ NlogN

 

 

 

힙 구성(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] 교환

    아니면

        탈출

 

힙 구성은 N-1 번 수행합니다. 그리고 힙 구성에 걸리는 비용은 트리의 높이가 제일 높을 때 최악이 나옵니다. 자식과 비교하면서 교환하므로 logN에 비례합니다. 따라서 전체 힙 구성에 걸리는 비용의 합은 NlogN보다 작습니다.

 

전체 힙 구성에 걸리는 비용의 합  ≤ Nlog(N)

 

따라서 힙 정렬에 드는 비용은 초기 힙 구성 비용(Nlog(N)보다 작음)과 전체 힙 구성에 걸리는 비용(NlogN보다 작음)이므로 2NlogN보다 작다고 할 수 있습니다. 따라서 빅 오 점근식 표기법으로 표현한다면 상수를 제거하여 O(NlogN)이라고 말할 수 있습니다.

 

일반적으로 퀵 정렬이 가장 빠르다고 알려졌지만 선택한 피벗의 성질에 따라 다른 성능을 보이기 때문에 실제로 가장 빠른 것은 아닙니다. 오히려 힙 정렬은 자료의 성질과 관계없이 안정적으로 O(NlogN)을 보장합니다. 이 외에도 앞으로 다룰 병합 정렬과 기수 정렬도 O(NlogN)성능을 보장하는 정렬 방식입니다.

 

 

 

 

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)

 

template <typename data, typename compare>

void heap_sort(data *base, size_t n, compare algo)

{

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

    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;

            }

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

            {

만약 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