힙정렬(heap sort)

힙정렬(heap sort)

---

힙 트리를 이용한 알고리즘

원리

1. 힙트리 구성 (힙의 규칙 유지 조건하)
2. 루트값 ↔ 마지막 값 ⇒ 정렬범위-1
3. 힙트리 재구성 (∵값 교환으로 힙성질 위배)
4. 반복

pseudocode

힙정렬(base : 배열시작주소, n : 배열요소 개수)

    1. 배열을 최대 힙으로 구성
        반복(i : n/2 - 1 -> 0)
            최대 힙을 구성하는 함수 호출 (base, n, i)

    2. 정렬 수행
        반복(i : n-1 -> 1)
            base[0]와 base[i] 교환  // 가장 큰 값을 배열의 마지막으로 이동
            최대 힙을 구성하는 함수 호출 (base, i, 0)  // 남은 부분을 최대 힙으로 재정렬

    최대 힙 구성 함수(base : 배열시작주소, n : 배열요소 개수, i : 현재 노드 인덱스)
        최대값을 현재 노드(i), 왼쪽 자식(2*i + 1), 오른쪽 자식(2*i + 2) 중에서 찾음
        최대값이 현재 노드(i)가 아니면
            현재 노드(i)와 최대값을 교환
            교환된 자리에 대해 최대 힙 구성 함수 재귀 호출

best case 시간복잡도 : $O(n$ $log$ $n)$
avg case 시간복잡도 : $O(n$ $log$ $n)$
worst case 시간복잡도 : $O(n$ $log$ $n)$
안정성 : 불안정
장점 : 추가 메모리 필요X,항상 $O(n$ $log$ $n)$의 시간복잡도
단점 : 데이터에 상태에 따라 동일한 시간 복잡도를 가지는 퀵정렬보다는 느리다

실제코드

#include <stdio.h>

//교환 함수
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void heapify(int arr[], int n, int i) {
    
    int largest = i; //부모
    int left = 2 * i + 1; //왼쪽 자식
    int right = 2 * i + 2; //오른쪽 자식

    // 왼쪽 자식이 더 큰 경우
    if (left < n && arr[left] > arr[largest])
        largest = left;

    // 오른쪽 자식이 더 큰 경우
    if (right < n && arr[right] > arr[largest])
        largest = right;

    // 가장 큰 값이 루트가 아닌 경우 스왑하고 재귀적으로 힙 조정
    if (largest != i) {
        swap(&arr[i], &arr[largest]);
        heapify(arr, n, largest);
    }
}

void heapSort(int arr[], int n) {
    // 배열을 처음부터 최대 힙으로 만드는 초기화 과정
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);
    // 하나씩 요소를 힙에서 제거하여 정렬 - 마지막요소와 루트 바꾸고 힙트리 재구성
        for (int i = n - 1; i > 0; i--) {
            // 루트와 마지막 요소를 교환
            swap(&arr[0], &arr[i]);
            
            // 남은 부분에 대해 힙 구조를 유지
            heapify(arr, i, 0);
        }
}

int main(int argc, const char * argv[]) {
    int arr[20] = {
        3, 5, 2, 2, 4,
        6, 1, 3, 7, 8,
        2, 11, 2, 21, 20,
        12, 14, 1, 6, 16
    };
    int n = sizeof(arr) / sizeof(int);
    heapSort(arr, n);
    // 정렬된 배열 출력
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
    return 0;
}