초보 자바 프로그래밍(23) - 힙정렬 (Heap Sort)

힙 정렬 대표 이미지

🔖 INDEX

 

 

힙 정렬(Heap Sort)은 이진 힙(Binary Heap)이라는 자료구조를 사용하여 배열을 정렬하는 비교 기반 정렬 알고리즘입니다. 이진 힙은 완전 이진 트리(Complete Binary Tree)로서, 부모 노드의 값이 자식 노드의 값보다 항상 크거나 작은 특성을 가집니다. 힙 정렬은 이 특성을 이용해 배열을 정렬합니다.

 

힙 정렬의 작동 원리

힙 정렬의 작동 원리는 다음과 같습니다: ​

1. 배열을 이진 힙으로 변환합니다. 배열을 이진 힙으로 변환하는 과정은 일반적으로 배열의 원소들을 차례대로 삽입하는 방식으로 구현됩니다. 이 과정에서 최대 힙(Max-Heap) 또는 최소 힙(Min-Heap) 중 하나를 선택해야 합니다. 최대 힙을 사용하면 오름차순으로 정렬되고, 최소 힙을 사용하면 내림차순으로 정렬됩니다.
2. 힙에서 최댓값(최솟값)을 추출하고, 배열의 마지막 원소와 교환합니다. 이 과정을 힙 추출(Heap Extraction)이라고 합니다. 이렇게 추출된 원소는 정렬된 위치에 놓이게 됩니다.
3. 힙 추출 후, 힙의 크기를 줄이고, 힙의 루트 노드를 다시 최댓값(최솟값)으로 만들어 줍니다. 이 과정을 힙 복원(Heap Restoration)이라고 합니다.
4. 2- 3단계를 힙의 크기가 1 이하가 될 때까지 반복합니다. 이 과정을 통해 배열이 완전히 정렬됩니다.

 

힙 정렬의 특징

힙 정렬의 특징은 다음과 같습니다: ​

1. 안정적이지 않은 정렬(Unstable Sort): 같은 값의 원소들이 정렬 과정에서 상대적인 순서가 변경될 수 있습니다.
2. 제자리 정렬(In-place Sort): 입력 배열 안에서 정렬이 이루어지며, 추가적인 메모리를 사용하지 않습니다.
3. 시간 복잡도(Time Complexity): 최선, 평균, 최악의 경우 모두 O(n log n)의 시간 복잡도를 가집니다. ​

 

 

힙 정렬의 장점

• 일관된 성능: 최악의 경우에도 O(n log n)의 시간 복잡도를 유지합니다. 이로 인해 일관된 성능이 요구되는 경우에 적합합니다.
• 메모리 사용량이 적음: 제자리 정렬 알고리즘으로서 추가적인 메모리를 사용하지 않습니다. 이로 인해 메모리 제약이 있는 상황에서도 사용할 수 있습니다.
• 외부 정렬에 적합: 힙 정렬은 외부 정렬(External Sorting)에 적합한 알고리즘입니다. 외부 정렬은 디스크와 같은 외부 저장소에 저장된 데이터를 정렬하는 과정에서 사용되며, 힙 정렬은 이 과정에서 효율적으로 사용할 수 있습니다. ​

 

힙 정렬의 단점

• 불안정한 정렬: 같은 값의 원소들이 정렬 과정에서 상대적인 순서가 변경될 수 있습니다. 이로 인해 안정성이 요구되는 경우에는 다른 알고리즘을 사용하는 것이 좋습니다.
• 상대적으로 느린 평균 속도: 평균적인 경우 퀵 정렬이나 병합 정렬보다 상대적으로 느린 속도를 보입니다. 그러나 최악의 경우에는 퀵 정렬보다 더 빠를 수 있습니다.

 

힙 정렬의 구현 예제

힙 정렬은 자바에서 다음과 같이 구현할 수 있습니다.

 

 

// HeapSort 클래스 선언
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;

        // 왼쪽 자식이 부모보다 크면 왼쪽 자식을 largest로 설정
        if (left < n && arr[left] > arr[largest]) {
            largest = left;
        }

        // 오른쪽 자식이 largest보다 크면 오른쪽 자식을 largest로 설정
        if (right < n && arr[right] > arr[largest]) {
            largest = right;
        }

        // largest가 i와 다른 경우 두 원소를 교환하고 하위 트리를 재귀적으로 정렬
        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;
    }
}

힙 정렬은 이진 힙 자료구조의 구현 방식에 크게 의존합니다. 이진 힙 구현의 성능과 효율성이 힙 정렬의 전체적인 성능에 영향을 줍니다. 따라서 효율적인 이진 힙 구현을 사용하는 것이 중요합니다. ​

 

또한 힙 정렬은 불안정한 정렬 알고리즘입니다. 따라서 안정성이 요구되는 경우에는 병합 정렬, 팀 정렬 등 안정적인 정렬 알고리즘을 사용하는 것이 좋습니다.