힙 정렬(Heap Sort) 알고리즘으로 10개 요소의 배열을 정렬하는 C++ 프로그램

힙 정렬(Heap Sort)은 이진 힙(Binary Heap) 자료구조를 기반으로 하는 정렬 알고리즘입니다. 이진 힙에서는 최대 힙(Max Heap)의 경우 부모 노드가 자식 노드보다 크거나 같고, 최소 힙(Min Heap)의 경우 부모 노드가 자식 노드보다 작거나 같습니다.

힙 정렬의 동작 과정

다음 예제를 통해 힙 정렬의 모든 단계를 살펴보겠습니다.

1단계: 원본 배열

정렬하기 전 10개 요소로 구성된 원본 배열은 다음과 같습니다.

2단계: 최대 힙 구성

이 배열은 max-heapify 연산을 사용하여 이진 최대 힙으로 변환됩니다. 배열 형태로 표현된 최대 힙은 다음과 같습니다.

3단계: 요소 추출 및 정렬 완성

최대 힙의 루트 요소(가장 큰 값)를 추출하여 배열의 맨 끝에 배치한 후, 나머지 요소들에 대해 max heapify를 호출해 다시 최대 힙을 만듭니다. 이 과정을 반복하면 최종적으로 정렬된 배열을 얻을 수 있습니다.

C++ 구현 코드

힙 정렬 알고리즘을 사용하여 10개 요소의 배열을 정렬하는 프로그램은 다음과 같습니다.

#include<iostream>
using namespace std;
void heapify(int arr[], int n, int i) {
    int temp;
    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) {
        temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;
        heapify(arr, n, largest);
    }
}
void heapSort(int arr[], int n) {
    int temp;
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);
    for (int i = n - 1; i >= 0; i--) {
        temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
        heapify(arr, i, 0);
    }
}
int main() {
    int arr[] = { 20, 7, 1, 54, 10, 15, 90, 23, 77, 25};
    int n = 10;
    int i;
    cout<<"Given array is: "<<endl;
    for (i = 0; i < n; i++)
    cout<<arr[i]<<" ";
    cout<<endl;
    heapSort(arr, n);
    printf("\nSorted array is: \n");
    for (i = 0; i < n; ++i)
    cout<<arr[i]<<" ";
}

실행 결과

Given array is:
20 7 1 54 10 15 90 23 77 25
Sorted array is:
1 7 10 15 20 23 25 54 77 90

코드 상세 설명

heapify() 함수

위 프로그램에서 heapify() 함수는 요소들을 힙 구조로 변환하는 역할을 합니다. 이 함수는 재귀 함수로, 호출된 위치의 요소(매개변수 i)부터 시작하여 최대 힙을 구성합니다. 해당 코드는 다음과 같습니다.

void heapify(int arr[], int n, int i) {
    int temp;
    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) {
        temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;
        heapify(arr, n, largest);
    }
}

이 함수는 먼저 현재 노드(i), 왼쪽 자식(l), 오른쪽 자식(r) 중 가장 큰 값을 찾습니다. 만약 자식 중 더 큰 값이 존재한다면 두 요소를 교환하고, 교환된 위치에서 다시 heapify()를 재귀적으로 호출하여 힙 속성을 유지합니다.

heapSort() 함수

heapSort() 함수는 힙 정렬 방식으로 배열 요소를 정렬합니다. 먼저 리프 노드가 아닌 노드들부터 시작해 각각에 대해 heapify()를 호출함으로써 전체 배열을 이진 최대 힙으로 변환합니다.

for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);

그다음, for 루프의 각 반복마다 루트 요소(최댓값)를 꺼내 배열의 끝에 배치하고, heapify()를 호출하여 나머지 요소들이 여전히 최대 힙을 유지하도록 합니다. 이 과정을 통해 모든 요소가 순서대로 힙에서 제거되며, 최종적으로 정렬된 배열이 완성됩니다.

for (int i = n - 1; i >= 0; i--) {
    temp = arr[0];
    arr[0] = arr[i];
    arr[i] = temp;
    heapify(arr, i, 0);
}

main() 함수

main() 함수에서는 먼저 원본 배열을 화면에 출력합니다. 그런 다음 heapSort() 함수를 호출하여 배열을 정렬합니다.

cout<<"Given array is: "<<endl;
for (i = 0; i < n; i++)
cout<<arr[i]<<" ";
cout<<endl;
heapSort(arr, n);

마지막으로 정렬이 완료된 배열을 출력합니다.

printf("\nSorted array is: \n");
for (i = 0; i < n; ++i)
cout<<arr[i]<<" ";

마무리

힙 정렬은 시간 복잡도가 O(n log n)으로 안정적인 성능을 보이는 정렬 알고리즘이며, 추가 메모리 공간이 거의 필요하지 않아 제자리(in-place) 정렬 방식으로 분류됩니다. 특히 최악의 경우에도 O(n log n)의 성능을 보장한다는 점에서 퀵 정렬과 차별화되는 장점이 있습니다.