[알고리즘]정렬-힙정렬(Heap Sort)

숭실대학교 컴퓨터학부의 알고리즘 수업을 들으며 정리한 내용입니다.
참고교재: 쉽게 배우는 알고리즘(문병로)

기본적인 정렬 알고리즘 O(n^2)
1.선택정렬
2.버블정렬
3.삽입정렬

고급 정렬 알고리즘 O(n*logn)
1.병합정렬
2.퀵정렬
3.힙정렬

특수 정렬 알고리즘 O(n)
1.계수정렬
2.기수정렬

 

정렬(Heap Sort)이란

힙 정렬(Heap Sort)은 완전 이진 트리를 바탕으로 한 정렬 방식입니다. 힙 정렬은 이진 힙(이진 트리의 한 종류)의 특징을 활용하여 정렬을 수행하며, 이진 힙에는 최대 힙(Max Heap)과 최소 힙(Min Heap)이 있습니다.

힙정렬의 과정,출처: 위키백과

힙 정렬의 기본 원리는 다음과 같습니다:

1. 먼저, 정렬되지 않은 배열을 최대 힙으로 변환합니다. 최대 힙이란 부모 노드가 자식 노드보다 크거나 같은 완전 이진 트리를 의미합니다.
2. 최대 힙에서 루트 노드(가장 큰 값)를 배열의 마지막 요소와 교환합니다.
3. 요소를 교환한 후, 교환한 요소를 제외하고 남은 배열을 다시 최대 힙으로 변환합니다.
4. 배열에 남아있는 요소가 없을 때까지 2번과 3번의 과정을 반복합니다.

힙 정렬의 시간 복잡도는 최악의 경우, 최선의 경우, 평균적으로 모두 O(n log n)입니다. 이는 정렬하고자 하는 배열의 크기를 n이라 할 때, n개의 요소를 힙에 넣는 작업이 log n이 걸리고, 이를 n번 반복하므로 n log n이 걸린다는 뜻입니다.

또한, 힙 정렬은 추가적인 메모리 공간을 필요로 하지 않는 '제자리 정렬(in-place sort)'에 속합니다. 이는 정렬을 위해 주어진 배열 외에 다른 추가적인 배열이나 리스트를 필요로 하지 않는다는 뜻입니다.

하지만, 힙 정렬은 정렬의 안정성(stability)이 보장되지 않습니다. 즉, 동일한 값을 가진 원소의 상대적 순서가 정렬 후에 보장되지 않습니다.

 

힙정렬 코드

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

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

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

    if (largest != i) {
        swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

void heapSort(int arr[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);

    for (int i=n-1; i>=0; i--) {
        swap(arr[0], arr[i]);
        heapify(arr, i, 0);
    }
}

테스트 코드

void printArray(int arr[], int n) {
    for (int i=0; i<n; ++i)
        cout << arr[i] << " ";
    cout << "\n";
}

int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(arr)/sizeof(arr[0]);

    cout << "Original array is \n";
    printArray(arr, n);

    heapSort(arr, n);

    cout << "Sorted array is \n";
    printArray(arr, n);
}

 

테스트 결과

Original array is
12 11 13 5 6 7
Sorted array is
5 6 7 11 12 13