[알고리즘 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] 교환

    아니면

        탈출

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

만약 rc가 n이면 왼쪽 자식만 있다는 것입니다. 왼쪽 자식이 자신보다 더 크면 자료를 교환하세요.

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

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

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

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

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

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

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

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


학습에 도움이 되시면 ebook을 구입(판매가 3000원, ebook)하여 소장하시면 감사하겠습니다.