[기초] C++ 알고리즘 : 힙 정렬 (Heap Sort)

---

 

힙 정렬(Heap Sort)은 힙(heap) 자료구조를 기반으로 한 정렬 알고리즘입니다.

이 알고리즘은 평균 및 최악의 경우에 모두 O(n log n)의 시간 복잡도를 가지며,

제자리 정렬(in-place sorting) 알고리즘 중 하나입니다.

힙 정렬은 주로 배열을 기반으로 작동하며, 추가적인 메모리 공간을 필요로 하지 않습니다.

 

---

 

일반적으로 다음과 같은 단계로 진행됩니다

 

• 주어진 배열을 최대 힙(Max Heap) 또는 최소 힙(Min Heap)으로 구성합니다.
  
  
• 최대 힙(또는 최소 힙)에서 가장 큰(또는 가장 작은) 요소를 추출하여 배열의 가장 뒤에 배치합니다.
  
  
• 배열에서 추출한 요소를 제외하고 다시 최대 힙(또는 최소 힙)을 유지합니다.
  
  
• 모든 요소가 정렬될 때까지 위 과정을 반복합니다.
  
  

#include <iostream>

// 힙 정렬 함수
void heapify(int arr[], int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    // 왼쪽 자식이 루트보다 크면 largest 갱신
    if (left < n && arr[left] > arr[largest])
        largest = left;

    // 오른쪽 자식이 루트보다 크면 largest 갱신
    if (right < n && arr[right] > arr[largest])
        largest = right;

    // largest가 루트가 아니면 교환
    if (largest != i) {
        swap(arr[i], arr[largest]);

        // 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); // 배열의 크기를 줄여서 힙 속성 유지
    }
}

// 배열 출력 함수
void printArray(int arr[], int size) {
    for (int i = 0; i < size; ++i) {
        cout << arr[i] << " ";
	}
    cout << "\n";
}

int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    std::cout << "정렬 전 배열: ";
    printArray(arr, n);

    heapSort(arr, n);

    std::cout << "정렬 후 배열: ";
    printArray(arr, n);

    return 0;
}

 

 

출력 결과

 

정렬 전 배열: 12 11 13 5 6 7 
정렬 후 배열: 5 6 7 11 12 13

 

 

 

제 글이 도움이 되셨다면 댓글 & 공감 부탁드려요 😀