[C언어 알고리즘] 3.5.3 힙 정렬 알고리즘 구현

[C언어 알고리즘] 3.5.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] 교환

    아니면

        탈출

//힙 정렬

#include <stdio.h>

먼저 두 개의 값을 교환하는 매크로 함수를 작성합니다.

#define SWAP(a,b)  {int t; t = a; a=b; b=t;}//a와 b를 교환

 

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

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

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

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

 

이 책에서는 정수 형식 배열을 정렬하는 함수를 만들기로 할게요.

void ViewArr(int *arr, int n);

void HeapSort(int *base, size_t n);

int main(void)

{

    int arr[10] = { 9,4,3,10,5,8,7,6,2,1 };

정렬 전에 배열 요소를 출력합시다.

    ViewArr(arr, 10);

    HeapSort(arr, 10);

정렬 후에 배열 요소를 출력합시다.

    ViewArr(arr, 10);

    return 0;

}

void HeapSort(int *base, size_t n)

{

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

    for (size_t i = 1; i<n; i++)

    {

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

        int j = i;

    

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

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

        {

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

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

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

            if (base[j]< base[pa]) //부모보다 크면

            {

                SWAP(base[j], base[pa]);//부모와 교환

정렬 과정을 출력하기 위한 코드입니다. 출력을 원하지 않으면 주석 처리하세요.

                ViewArr(base, n);

                j = pa;

            }

            else

            {

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

                break;

            }

        }

    }

 

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

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

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

    ViewArr(base, n);

    n--;

C 컴파일러 버전에 따라 변수 선언을 중간에 할 수 없다면 변수 선언문은 함수 시작부로 올려서 작성하세요.

    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 (base[me]< base[lc])

                {

                    SWAP(base[me], base[lc]);

정렬 과정을 출력하기 위한 코드입니다. 출력을 원하지 않으면 주석 처리하세요.

                    ViewArr(base, n);

                }

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

                break;

            }

 

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

            int bc = lc;

            if (base[lc]< base[rc])

            {

                bc = rc;

            }

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

                  if (base[bc]> base[me])

            {

                SWAP(base[bc], base[me]);

정렬 과정을 출력하기 위한 코드입니다. 출력을 원하지 않으면 주석 처리하세요.

                ViewArr(base, n);

                me = bc;

            }

            else

            {

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

                break;

            }

        }

 

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

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

        ViewArr(base, n);

        n--;

    }

}

테스트 목적으로 배열의 내용을 출력하는 함수입니다.

void ViewArr(int *arr, int n)

{

    int i = 0;

인덱스 0에서 마지막 요소까지 값을 출력합니다.

    for (i = 0; i<n; i++)

    {

        printf("%2d ", arr[i]);

    }

전체 요소 값을 출력한 후에 개행 문자를 출력합니다.

    printf("\n");

}