[java] 힙 정렬 알고리즘

15 Dec 2023

java

힙 정렬(Heap Sort)은 특정 정렬 알고리즘 중 하나입니다. 이 알고리즘은 거의 정렬된 배열에도 잘 작동하고, 대규모 데이터셋에서 빠르게 작동합니다.

힙 정렬 알고리즘

힙 정렬 알고리즘의 주요 단계는 다음과 같습니다:

주어진 배열을 이진 트리 형태인 힙(heap)으로 구성합니다.
최대 힙 또는 최소 힙을 구성하여 루트 노드를 기준으로 정렬합니다.
루트 노드를 제거하고, 힙 구조를 다시 조정하여 새로운 힙을 구성합니다.
이러한 과정을 반복하여 전체 배열을 정렬합니다.

자바로 구현된 힙 정렬

다음은 자바를 사용하여 힙 정렬을 구현한 예시 코드입니다:

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

이제 이 코드를 이용하여 힙 정렬 알고리즘을 실행할 수 있습니다.

마무리

힙 정렬 알고리즘은 효율적으로 동작하며 다양한 상황에서 사용할 수 있습니다. 이 알고리즘을 이해하고 구현하는 것은 자료 구조와 알고리즘에 대한 학습에 도움이 될 것입니다.

더 많은 정보를 원하신다면 아래 출처를 참고하세요.

출처: GeeksforGeeks - Heap Sort