[java] 자바에서 힙 정렬 구현하기

15 Dec 2023

java

힙 정렬(Heap Sort)은 오름차순이나 내림차순으로 정렬하는 효율적인 알고리즘 중 하나입니다. 이 알고리즘은 배열을 이용하여 작동하며, 최대 힙 구조를 활용하여 정렬을 수행합니다.

힙 정렬 알고리즘

힙 정렬의 주요 단계는 다음과 같습니다.

주어진 배열을 최대 힙으로 구성합니다.
최상위 루트 노드를 배열의 가장 마지막 요소와 교환합니다.
배열의 크기를 1만큼 줄이고, 최상위 노드에 대해 최대 힙 속성을 복원합니다.
위 단계를 반복하여 정렬을 완료합니다.

자바 코드 예시

다음은 자바로 힙 정렬을 구현하는 예시 코드입니다.

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);
        }
    }
}

public class Main {
    public static void main(String args[]) {
        int arr[] = {12, 11, 13, 5, 6, 7};
        int n = arr.length;

        HeapSort ob = new HeapSort();
        ob.sort(arr);

        System.out.println("정렬된 배열:");
        for (int i=0; i<n; ++i)
            System.out.print(arr[i] + " ");
    }
}

위 코드는 주어진 배열을 힙 정렬하는 효율적인 방법을 구현한 것입니다.

힙 정렬은 자료 구조인 힙을 이용하기 때문에 다른 고급 정렬 알고리즘보다 복잡해 보일 수 있지만, 성능 면에서 매우 우수합니다.

결론

힙 정렬은 자바를 포함한 다양한 언어로 구현할 수 있으며, 효율적인 정렬 알고리즘이기 때문에 대규모 데이터 정렬에 많이 사용됩니다.

참고 자료