[c++] 힙 정렬 알고리즘

08 Dec 2023

힙 정렬 알고리즘은 배열을 이진 트리로 간주하여 정렬하는 알고리즘 중 하나입니다. 힙 정렬은 주어진 배열을 힙 자료구조로 변환하고, 최대 힙을 구성한 뒤 루트 노드와 배열의 마지막 요소를 교환하여 정렬을 수행합니다.

알고리즘 동작

주어진 배열을 최대 힙으로 만듭니다.
최대 힙에서 루트 노드(가장 큰 요소)를 제거하고 배열의 마지막 요소와 교환합니다.
교환이 이루어진 후에는 배열의 마지막 요소가 최대값이 되므로, 이를 제외하고 나머지 배열을 다시 최대 힙으로 만듭니다.
남은 요소가 없을 때까지 위의 과정을 반복하여 배열을 정렬합니다.

C++ 코드 예시

#include <iostream>
using namespace std;

void heapify(int arr[], int n, int i) {
    int largest = i;
    int l = 2 * i + 1;
    int r = 2 * i + 2;

    if (l < n && arr[l] > arr[largest]) {
        largest = l;
    }

    if (r < n && arr[r] > arr[largest]) {
        largest = r;
    }

    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 arr[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    heapSort(arr, n);

    cout << "정렬된 배열: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    return 0;
}

위의 코드는 C++로 구현된 힙 정렬 알고리즘의 예시입니다.

힙 정렬을 수행하는 heapify 함수와 heapSort 함수가 정의되어 있습니다. heapSort 함수는 최대 힙을 구성하고 배열을 정렬하는 역할을 합니다. main 함수에서는 테스트를 위한 배열을 생성하고 heapSort 함수를 호출하여 정렬된 배열을 출력합니다.

참고 문헌: