힙 정렬 (Heap Sort)을 이해하고 C#으로 구현해보자!

안녕하세요, 여러분! 오늘은 기술 면접에서 자주 다루는 주제 중 하나인 힙 정렬(Heap Sort)에 대해 이야기해볼까 합니다. 힙 정렬은 효율적인 정렬 알고리즘 중 하나로, 이진 힙 자료구조를 기반으로 합니다. 이 포스팅에서는 힙 정렬의 기본 개념부터 C#을 이용한 구현까지 자세히 살펴보도록 하겠습니다.

힙 정렬(Heap Sort)이란?

힙 정렬은 비교 기반 정렬 알고리즘 중 하나입니다. 이 알고리즘은 이진 힙의 속성을 이용해 리스트를 정렬합니다. 이진 힙은 완전 이진 트리의 일종으로, 각 노드의 키 값이 그 자식의 키 값보다 크거나 같은 (또는 작거나 같은) 경우를 말합니다. 이런 특성 덕분에 힙 정렬은 O(n log n)의 시간 복잡도를 가집니다.

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

1. 배열을 최대 힙 구조로 만듭니다. 최대 힙이란 모든 노드가 자식 노드보다 큰 값을 가지는 이진 트리를 말합니다.
2. 가장 큰 값(루트에 위치)을 배열의 마지막 요소와 교환하고, 힙 크기를 하나 줄입니다.
3. 교환 후에도 최대 힙 속성이 유지되도록 재정렬합니다.
4. 힙 크기가 1보다 클 때까지 이 과정을 반복합니다.

이제 C#을 이용해 힙 정렬 알고리즘을 구현해보도록 하겠습니다.

C#을 사용한 힙 정렬 구현

public class HeapSort
{
    public void Sort(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
    void Heapify(int[] arr, int n, int i)
    {
        int largest = i;  // Initialize largest as root
        int left = 2 * i + 1;  // left = 2*i + 1
        int right = 2 * i + 2;  // right = 2*i + 2

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

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

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

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

 

이 코드는 힙 정렬 알고리즘을 C#으로 구현한 것입니다. 먼저 Sort 메서드에서 배열을 최대 힙 구조로 만든 후, 각 요소를 추출하여 정렬합니다. Heapify 메서드는 주어진 서브트리를 최대 힙 구조로 만드는데 사용됩니다.

 

힙 정렬은 각 요소를 힙에 넣었다가 다시 꺼내는 과정을 거치므로, 이 과정이 끝나면 배열은 오름차순으로 정렬된 상태가 됩니다. 이 알고리즘의 시간 복잡도는 O(n log n)으로, 큰 데이터 세트에 대한 정렬에 효율적입니다.

 

힙 정렬 알고리즘의 이해와 구현은 컴퓨터 과학 학습에 중요한 부분이며, 기술 면접에서도 종종 나오는 주제입니다. 여러분이 이 포스팅을 통해 힙 정렬에 대해 좀 더 이해하였기를 바랍니다.

 

다음 포스팅에서는 또 다른 흥미로운 알고리즘 주제로 돌아오겠습니다. 그 때까지 계속해서 학습하시고, 좋은 결과 얻으시길 바랍니다!

이상으로 오늘의 포스팅을 마치겠습니다. 감사합니다!