힙 정렬이란?
힙 정렬(Heap Sort)은 힙(heap) 자료구조를 활용하는 비교 기반 정렬 알고리즘입니다. 매번 힙의 루트 요소, 즉 가장 큰 값을 꺼내 배열에 저장하고, 그 자리를 가장 오른쪽 리프(잎) 요소로 대체한 뒤 힙 구조를 다시 구성하는 방식으로 동작합니다. 이 과정을 힙에 더 이상 요소가 남아 있지 않을 때까지 반복하면 배열이 오름차순으로 정렬됩니다.
힙 정렬은 최악의 경우에도 시간 복잡도가 O(n log n)으로 보장되며, 추가적인 메모리 공간이 거의 필요하지 않다는 장점이 있어 안정적인 성능이 요구되는 환경에서 유용하게 사용됩니다.
다음은 C#으로 힙 정렬을 구현한 프로그램입니다.
예제 코드
using System;
namespace HeapSortDemo {
public class example {
static 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--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapify(arr, i, 0);
}
}
static 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) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
heapify(arr, n, largest);
}
}
public static void Main() {
int[] arr = {55, 25, 89, 34, 12, 19, 78, 95, 1, 100};
int n = 10, i;
Console.WriteLine("Heap Sort");
Console.Write("Initial array is: ");
for (i = 0; i < n; i++) {
Console.Write(arr[i] + " ");
}
heapSort(arr, 10);
Console.Write("\nSorted Array is: ");
for (i = 0; i < n; i++) {
Console.Write(arr[i] + " ");
}
}
}
}
실행 결과
위 프로그램을 실행하면 다음과 같은 결과가 출력됩니다.
Heap Sort Initial array is: 55 25 89 34 12 19 78 95 1 100 Sorted Array is: 1 12 19 25 34 55 78 89 95 100
이제 위 프로그램이 어떻게 동작하는지 단계별로 자세히 살펴보겠습니다.
1. Main() 함수 – 초기 배열 출력 및 정렬 호출
Main() 함수에는 정렬할 배열 arr이 선언되어 있습니다. 먼저 초기 배열을 화면에 출력한 후, 배열을 실제로 정렬하는 heapSort() 함수를 호출합니다. 해당 코드는 다음과 같습니다.
int[] arr = {55, 25, 89, 34, 12, 19, 78, 95, 1, 100};
int n = 10, i;
Console.WriteLine("Heap Sort");
Console.Write("Initial array is: ");
for (i = 0; i < n; i++) {
Console.Write(arr[i] + " ");
}
heapSort(arr, 10);
2. heapSort() 함수 – 힙 생성
heapSort() 함수는 가장 먼저 주어진 요소들을 힙 구조로 변환합니다. 이 과정은 for 루프를 사용해 힙의 모든 리프가 아닌(non-leaf) 요소에 대해 heapify() 함수를 호출하는 방식으로 수행됩니다. 리프가 아닌 요소는 인덱스 n/2 - 1부터 0까지 역순으로 순회합니다.
for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i);
3. heapSort() 함수 – 루트 요소 제거 및 힙 재구성
힙이 완성된 후에는 for 루프를 사용해 힙의 루트 요소, 즉 가장 큰 값을 하나씩 제거합니다. 제거된 루트 자리는 가장 오른쪽 리프 요소와 교체되며, 이후 heapify()를 다시 호출해 힙 속성을 재확립합니다. 이렇게 하면 큰 값들이 배열의 뒤쪽부터 차례대로 정렬되어 쌓이게 됩니다.
for (int i = n-1; i>=0; i--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapify(arr, i, 0);
}
4. heapify() 함수 – 힙 속성 유지
heapify() 함수는 요소들을 규칙에 맞게 배치하여 힙 구조를 만드는 핵심 역할을 담당합니다. 이 과정은 인덱스 i에 있는 요소에서 시작되며, 해당 요소는 heapify() 함수 입장에서 루트로 간주됩니다. 왼쪽 자식(2*i + 1)과 오른쪽 자식(2*i + 2)의 값을 현재 노드와 비교하여 세 값 중 가장 큰 값을 루트 위치로 올리고, 교환이 발생했으면 재귀적으로 heapify()를 호출해 아래쪽 하위 트리도 계속 정렬합니다.
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) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
heapify(arr, n, largest);
}
5. 정렬된 배열 출력
모든 정렬 과정이 끝나면 마지막으로 Main() 함수에서 정렬된 배열을 화면에 출력합니다.
Console.Write("\nSorted Array is: ");
for (i = 0; i < n; i++) {
Console.Write(arr[i] + " ");
}
마무리
지금까지 C#에서 힙 정렬을 구현하는 전체 과정을 살펴보았습니다. 힙 생성 → 루트 추출 → 힙 재구성의 반복이라는 핵심 흐름만 이해하면, 어떤 데이터에도 O(n log n)의 일관된 성능으로 정렬을 적용할 수 있습니다. 퀵 정렬처럼 평균 성능이 빠르지만 최악의 경우 O(n²)까지 느려질 수 있는 알고리즘과 달리, 힙 정렬은 성능이 안정적이어야 하는 시스템에서 특히 유용한 선택입니다.