[C++로 배우는 알고리즘과 자료구조] Day 20: 힙 정렬 (Heap Sort)

힙 정렬 (Heap Sort)

힙 정렬은 이진 힙을 이용한 정렬 알고리즘으로, 최대 힙 또는 최소 힙을 사용하여 배열을 정렬합니다. 힙 정렬은 평균 및 최악의 경우 시간 복잡도가 (O(n \log n))입니다.

힙 정렬의 주요 단계:

1. 힙 구성 (Heapify): 배열을 이진 힙으로 변환합니다.
2. 정렬 (Sort): 힙의 루트 요소를 제거하고, 힙을 재구성하여 정렬된 배열을 만듭니다.

힙 정렬의 시간 복잡도:

• 평균의 경우: (O(n \log n))
• 최악의 경우: (O(n \log n))
• 최선의 경우: (O(n \log n))

힙 정렬 구현

힙 구성 함수

힙 속성을 유지하면서 배열을 이진 힙으로 변환합니다.

#include <iostream>
#include <vector>

// 힙 구성 함수
void heapify(std::vector<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) {
        std::swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

 

힙 정렬 함수

힙을 구성한 후, 루트 요소를 제거하여 정렬된 배열을 만듭니다.

// 힙 정렬 함수
void heapSort(std::vector<int>& arr) {
    int n = arr.size();

    // 배열을 힙으로 변환
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }

    // 힙에서 요소를 하나씩 추출하여 정렬
    for (int i = n - 1; i >= 0; i--) {
        std::swap(arr[0], arr[i]);
        heapify(arr, i, 0);
    }
}

int main() {
    std::vector<int> arr = {12, 11, 13, 5, 6, 7};

    std::cout << "정렬 전 배열: ";
    for (int value : arr) {
        std::cout << value << " ";
    }
    std::cout << std::endl;

    heapSort(arr);

    std::cout << "정렬 후 배열: ";
    for (int value : arr) {
        std::cout << value << " ";
    }
    std::cout << std::endl;

    return 0;
}

 

설명

1. 힙 구성 함수 (Heapify Function):
   • 주어진 노드를 루트로 하는 서브트리가 힙 속성을 만족하도록 합니다.
   • 재귀적으로 자식 노드와 비교하여 필요한 경우 자리를 바꾸고, 힙 속성을 유지합니다.
2. 힙 정렬 함수 (Heap Sort Function):
   • 배열을 힙으로 변환한 후, 루트 요소를 제거하여 정렬된 배열을 만듭니다.
   • 루트 요소와 배열의 마지막 요소를 교환한 후, 힙의 크기를 줄이고 다시 힙 속성을 유지합니다.

힙 정렬의 기본 개념과 구현 방법을 이해했습니다. 다음 단계로 넘어가며, 더 복잡한 정렬 알고리즘과 다양한 알고리즘을 학습해보겠습니다.

질문이나 피드백이 있으면 언제든지 댓글로 남겨 주세요. 내일은 "Day 21: 기수 정렬과 계수 정렬"에 대해 학습하겠습니다.