| 작성자 | 장원준 |
| 일 시 | 2024. 10. 08 (화) 18:00 ~ 21:00 |
| 장 소 | 복지관 b128-1호 |
| 참가자 명단 | 임혜진, 이재영, 성창민, 장원준, 김명원 |
| 사 진 |  |
Heap Sort (힙정렬)
힙 정렬(Heap Sort)은 완전 이진 트리(Complete Binary Tree) 구조를 기반으로 하는 효율적인 정렬 알고리즘입니다. 힙 정렬은 안정 정렬은 아니지만, 비교 기반 정렬 중에서는 시간 복잡도가 O(n log n)으로 상당히 빠르기 때문에 많은 상황에서 유용하게 쓰입니다. 이 글에서는 힙 정렬의 원리, 알고리즘 동작 방식, 장단점, 그리고 코드 구현 방법에 대해 자세히 살펴보겠습니다.
1. 힙(Heap)이란?
힙 정렬을 이해하기 위해 먼저 힙(Heap)에 대해 알아보겠습니다. 힙은 이진 트리의 한 종류로, 다음과 같은 두 가지 조건을 만족하는 트리를 말합니다:
- 완전 이진 트리(Complete Binary Tree): 모든 레벨에서 노드가 채워져 있어야 하며, 마지막 레벨에서는 왼쪽부터 차례대로 노드가 채워져 있어야 합니다.
- 힙 속성(Heap Property):
- 최대 힙(Max-Heap): 부모 노드가 자식 노드보다 크거나 같다. 즉, 트리의 루트에 가장 큰 값이 위치합니다.
- 최소 힙(Min-Heap): 부모 노드가 자식 노드보다 작거나 같다. 즉, 트리의 루트에 가장 작은 값이 위치합니다.
힙 정렬에서는 최대 힙을 주로 사용하여 가장 큰 값을 배열의 끝으로 보내고, 남은 트리를 다시 힙 구조로 정렬하는 과정을 반복합니다.
2. 힙 정렬의 동작 원리
힙 정렬은 다음과 같은 두 가지 주요 단계로 구성됩니다:
- 힙 구성(Build Heap): 주어진 배열을 힙 구조로 변환합니다. 최대 힙을 구성하여 배열의 루트에 가장 큰 값이 위치하도록 합니다.
- 힙 정렬(Heapify): 힙에서 루트 값을 추출하여 배열의 끝에 배치한 후, 나머지 부분에 대해 다시 힙 구조를 유지하도록 조정합니다. 이 과정을 반복하면 배열이 정렬됩니다.
힙 정렬은 배열의 인덱스를 이용하여 트리를 나타냅니다. 예를 들어, 인덱스 i의 왼쪽 자식 노드는 2i + 1에, 오른쪽 자식 노드는 2i + 2에 위치합니다. 부모 노드는 (i - 1) // 2로 찾을 수 있습니다.
힙 정렬의 구체적인 과정
- 배열을 최대 힙으로 변환: 주어진 배열을 최대 힙으로 구성합니다. 이때 배열의 중간부터 시작하여 각 부모 노드에 대해 힙 속성을 만족하도록 조정합니다.
- 최대 힙에서 가장 큰 요소를 정렬된 위치로 이동: 루트 노드는 배열에서 가장 큰 값이므로 이를 배열의 마지막 요소와 교환한 후, 배열의 길이를 하나 줄이고 다시 힙 구조를 유지하도록 조정합니다.
- 과정 반복: 배열이 완전히 정렬될 때까지 이 과정을 반복합니다.
3. 힙 정렬 알고리즘 단계별 예시
아래는 배열 [4, 10, 3, 5, 1]을 힙 정렬하는 과정입니다
Step 1: 최대 힙 구성
배열을 최대 힙으로 변환합니다.
- 인덱스 1 (10)과 그 자식들을 비교합니다. 최대 힙 속성이 만족되므로 그대로 유지됩니다.
- 인덱스 0 (4)과 자식들(10, 3)을 비교합니다. 10이 더 크므로 교환하여 [10, 4, 3, 5, 1]이 됩니다.
최대 힙 구조: [10, 4, 3, 5, 1]
Step 2: 정렬 시작
가장 큰 값인 루트 노드(10)를 배열의 마지막 요소(1)와 교환합니다. 배열 길이를 하나 줄이고 나머지 요소에 대해 힙 속성을 유지합니다.
- [1, 4, 3, 5, 10] → 1을 힙으로 정렬하여 [5, 4, 3, 1, 10]으로 만듭니다.
Step 3: 다시 힙 정렬
- [5, 4, 3, 1, 10]에서 5와 1을 교환하고 [1, 4, 3]을 다시 힙 정렬하여 [4, 1, 3]으로 바꿉니다.
이 과정을 반복하면 최종적으로 정렬된 배열 [1, 3, 4, 5, 10]을 얻게 됩니다.
4. 힙 정렬의 장단점
장점:
- 시간 복잡도 O(n log n): 힙 정렬의 시간 복잡도는 항상 O(n log n)으로, 퀵 정렬과 같은 최악의 경우에도 O(n²)이 아닌 안정적인 성능을 보입니다.
- 추가 메모리가 필요 없음: 힙 정렬은 배열 내에서 정렬이 이루어지기 때문에 추가적인 메모리 공간이 필요하지 않습니다.
단점:
- 안정 정렬이 아님: 같은 값을 가진 요소들의 상대적인 순서가 보장되지 않습니다.
- 캐시 효율이 낮음: 배열을 트리 구조로 표현하여 요소를 자주 교환하기 때문에 캐시를 덜 효율적으로 사용할 수 있습니다.
Heap sort 알고리즘에 대해 공부해보며 배열을 트리구조로 정리하는 방법도 효율적일 수 있음을 알게되었다. 그러나 캐시 효율이 낮은점에서 상황에 따라선 비효율적인 부분을 확인해야한다는 것도 느꼈다
메모리 효율이 중요할 때 참고해야겠다..!