[java] 자바의 힙 정렬(Heap Sort) 알고리즘 이해하기

14 Dec 2023

java

힙 정렬(Heap Sort)은 효율적인 정렬 알고리즘 중 하나로, 힙 자료구조를 기반으로 합니다.
이 알고리즘은 특히 대규모 데이터 집합에 대한 정렬에 적합하며, 안정적인 정렬 방법 중 하나입니다.

힙 정렬 알고리즘 개요

힙 정렬은 주어진 배열을 최대 힙 혹은 최소 힙으로 구성한 뒤, 힙의 성질을 이용하여 정렬을 수행합니다.
힙 정렬의 과정은 다음과 같습니다:

최대 힙 또는 최소 힙 구축: 주어진 배열을 힙 자료구조로 구성합니다.
루트 노드와 말단 노드 교환: 최상위 노드(최대 힙의 경우 최대값)를 배열의 말단 노드로 이동시키고, 힙의 크기를 줄입니다.
다시 힙으로 구성: 힙의 크기를 줄인 후, 교환된 노드를 포함하여 다시 힙을 구성합니다.
반복: 2번부터 3번까지의 과정을 반복하면서 정렬을 완성합니다.

힙 정렬의 시간 복잡도

힙 정렬의 시간 복잡도는 O(nlogn)으로, 평균 및 최악의 경우에도 동일한 효율성을 보입니다.
이러한 특성으로 인해 대규모 데이터 정렬에 적합한 알고리즘이라고 할 수 있습니다.

자바 코드 예제

다음은 자바로 구현된 힙 정렬의 간단한 예제 코드입니다.

public class HeapSort {
    public void heapSort(int arr[]) {
        int n = arr.length;

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

        // One by one extract an element from heap
        for (int i = n - 1; i > 0; i--) {
            // Move current root to end
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

            // call max heapify on the reduced heap
            heapify(arr, i, 0);
        }
    }

    // To heapify a subtree rooted with node i which is
    // an index in arr[]. n is size of heap
    void heapify(int arr[], int n, int i) {
        int largest = i; // Initialize largest as root
        int l = 2 * i + 1; // left = 2*i + 1
        int r = 2 * i + 2; // right = 2*i + 2

        // If left child is larger than root
        if (l < n && arr[l] > arr[largest])
            largest = l;

        // If right child is larger than largest so far
        if (r < n && arr[r] > arr[largest])
            largest = r;

        // If largest is not root
        if (largest != i) {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;

            // Recursively heapify the affected sub-tree
            heapify(arr, n, largest);
        }
    }
}

위의 코드는 힙 정렬을 수행하는 HeapSort 클래스의 예시입니다.

힙 정렬은 빠른 속도와 안정성으로 많은 애플리케이션에서 사용되며, 자바를 포함한 여러 언어에서 구현될 수 있습니다.

결론

힙 정렬은 대규모 데이터의 정렬에 효과적이며, 일반적으로 퀵 정렬과 비슷한 성능을 보입니다.
이 알고리즘은 안정적인 정렬 방법이기도 하며, 이를 통해 데이터의 순서를 보존할 수 있습니다.

더 많은 기술적인 내용을 찾으시려면 명세서를 확인하시기 바랍니다.

힙 정렬 알고리즘 Java 구현.