정렬 알고리즘 (6): 힙 정렬 (Heap Sort)

1. 힙 정렬이란?

힙 정렬(Heap Sort)은 "힙(Heap)" 자료구조를 활용하여 데이터를 정렬하는 비교 기반 정렬 알고리즘이다. 힙은 완전 이진 트리의 특성을 가지며, 최대 힙(Max Heap)과 최소 힙(Min Heap)으로 나눌 수 있다. 힙 정렬은 평균 및 최악의 경우 O(n log n)의 성능을 보장하며, 추가적인 메모리 공간을 거의 사용하지 않는 효율적인 정렬 알고리즘이다.

2. 힙 정렬의 동작 원리

힙 정렬은 다음과 같은 단계로 동작한다.

2.1 정렬 과정

1. 주어진 배열을 힙 자료구조로 변환한다 (Heapify 과정).
2. 최대 힙을 사용하여 가장 큰 요소를 배열의 끝으로 이동시킨다.
3. 힙 크기를 줄이고, 다시 힙을 재정렬(Heapify)하여 최대값을 루트로 유지한다.
4. 위 과정을 반복하여 배열이 완전히 정렬될 때까지 수행한다.

2.2 예제 코드 (Java)

public class HeapSort {
    // 힙 정렬 메서드
    public static void heapSort(int[] arr) {
        int n = arr.length;
        
        // 최대 힙 구성
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }
        
        // 힙에서 요소를 하나씩 꺼내어 정렬
        for (int i = n - 1; i > 0; i--) {
            swap(arr, 0, i); // 최대값을 끝으로 이동
            heapify(arr, i, 0); // 힙 크기를 줄이고 다시 정렬
        }
    }

    // 힙을 유지하는 메서드
    private 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) {
            swap(arr, i, largest);
            heapify(arr, n, largest);
        }
    }

    // 두 요소를 교환하는 메서드
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    // 힙 정렬 실행 및 결과 출력
    public static void main(String[] args) {
        int[] data = {64, 34, 25, 12, 22, 11, 90};
        System.out.println("정렬 전: ");
        for (int num : data) {
            System.out.print(num + " ");
        }
        
        heapSort(data);
        
        System.out.println("\n정렬 후: ");
        for (int num : data) {
            System.out.print(num + " ");
        }
    }
}

3. 힙 정렬의 성능 분석

힙 정렬의 시간 및 공간 복잡도를 분석하면 다음과 같다.

3.1 시간 복잡도

• 최선의 경우 (Best Case): O(n log n)
• 평균의 경우 (Average Case): O(n log n)
• 최악의 경우 (Worst Case): O(n log n)

힙 정렬은 항상 O(n log n)의 성능을 보장하는 비교 기반 정렬 알고리즘이다.

3.2 공간 복잡도

• 공간 복잡도: O(1) → 추가적인 배열을 사용하지 않고, 주어진 배열 내에서 정렬 수행 (In-place 알고리즘)

4. 힙 정렬의 장점과 단점

4.1 장점

• 최악의 경우에도 O(n log n)의 성능을 보장한다.
• 추가적인 메모리 공간이 거의 필요하지 않다.
• 안정적인 성능을 제공하며, 데이터 크기가 커질수록 효율적이다.

4.2 단점

• 다른 O(n log n) 알고리즘(퀵 정렬, 병합 정렬)보다 실질적인 성능이 낮을 수 있다.
• 데이터가 거의 정렬된 경우에도 O(n log n)의 연산이 필요하다.
• 안정 정렬(Stable Sort)이 아니며, 같은 값의 순서가 유지되지 않을 수 있다.

5. 힙 정렬의 활용 및 개선 방법

5.1 활용 사례

• 우선순위 큐(Priority Queue) 구현
• 실시간 데이터 정렬 (예: 스트리밍 데이터 분석)
• 메모리 사용량을 줄이면서 정렬이 필요한 경우

5.2 개선 방법

• 힙 생성 최적화: 힙을 만들 때 O(n) 방식으로 구성하는 방법 사용
• 하이브리드 정렬: 작은 배열에서는 삽입 정렬과 혼합하여 성능 최적화

6. 결론

힙 정렬은 O(n log n)의 안정적인 성능을 보장하는 효율적인 정렬 알고리즘이다. 추가적인 메모리 공간을 사용하지 않기 때문에 메모리 효율이 중요한 환경에서 유용하다. 하지만 실제 성능은 퀵 정렬이나 병합 정렬보다 낮을 수 있어, 특정한 상황에서 적절히 활용하는 것이 중요하다.