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에서 공통으로 사용할 코드를 이용하세요.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

▷ 실행 결과


전체 실습 결과물은 언제나 휴일 프로그램 소스 사이트에 있습니다.