[java] 자바 힙 정렬 알고리즘

08 Dec 2023

java

힙 정렬(Heap Sort)은 1964년 J.W.J. Williams에 의해 발명된 정렬 알고리즘으로, 특히 큰 데이터 집합을 정렬하는 데 뛰어난 성능을 보입니다. 힙 정렬은 특히 데이터 구조인 힙(Heap)을 기반으로 하며, 선택 정렬(Selection Sort)과 비슷한 알고리즘이지만 효율적인 대체 방법으로 널리 사용됩니다.

힙 정렬 알고리즘

힙 정렬 알고리즘은 다음과 같은 단계로 진행됩니다.

배열을 최대 힙(Max Heap)으로 구성한다.
최대 힙에서 최대값(루트)를 가져와 배열의 마지막 요소와 교환한다.
배열의 크기를 하나 줄이고, 최대 힙을 다시 구성한다.
위 과정을 반복하여 정렬을 완료한다.

이러한 알고리즘은 재귀적으로 최대 힙을 구성하고, 최대값을 루트와 교환하여 배열을 정렬하므로 O(n log n)의 시간 복잡도를 갖습니다.

public class HeapSort {
    public void sort(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--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

            heapify(arr, i, 0);
        }
    }

    void heapify(int[] arr, int n, int i) {
        int largest = i;
        int l = 2 * i + 1;
        int r = 2 * i + 2;

        if (l < n && arr[l] > arr[largest])
            largest = l;

        if (r < n && arr[r] > arr[largest])
            largest = r;

        if (largest != i) {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;

            heapify(arr, n, largest);
        }
    }
}

위의 코드는 자바로 힙 정렬을 구현한 예시입니다. sort 메서드에서 배열을 최대 힙으로 만들고, 배열을 정렬하는 과정을 담고 있습니다.

결론

힙 정렬은 효율적인 정렬 알고리즘으로, 대규모 데이터셋을 빠르게 정렬할 수 있는 장점을 가지고 있습니다. 반면, 추가적인 공간이 필요하다는 단점이 있지만, 정렬 시간이 중요한 경우 효율적인 선택일 수 있습니다.

자바를 포함한 다양한 언어로 힙 정렬을 구현할 수 있으며, 이를 활용하여 효율적인 데이터 정렬을 수행할 수 있습니다.

힙 정렬 알고리즘

결론

참고 자료