힙 정렬
힙 정렬 (Heap Sort)
힙 정렬(Heap Sort)은 힙(Heap) 자료구조를 이용하여 데이터를 정렬하는 알고리즘입니다. 항상 O(n log n)의 시간 복잡도를 보장하면서도, 추가적인 메모리 공간을 거의 사용하지 않는 '제자리 정렬(In-place Sort)'이 가능하다는 장점이 있습니다.
🔥 힙 정렬의 동작 원리
힙 정렬은 크게 '힙 구성'과 '정렬'의 두 단계로 이루어집니다. (오름차순 정렬을 위해 '최대 힙'을 사용하는 경우)
1. 1단계: 힙 구성 (Heap Construction) > * 정렬되지 않은 배열을 '최대 힙(Max Heap)' 구조로 변환합니다. 최대 힙은 부모 노드가 항상 자식 노드보다 큰 값을 가지므로, 루트 노드는 배열의 최댓값을 가집니다. > * 이 과정은 O(n)의 시간 복잡도를 가집니다.
2. 2단계: 정렬 (Sorting) > 1. 힙의 루트 노드(현재 배열의 최댓값)를 배열의 마지막 원소와 교환합니다. > 2. 배열의 크기를 1 줄여, 정렬된 마지막 원소(최댓값)를 힙에서 제외시킵니다. > 3. 새로운 루트 노드에 대해 '힙 재구성(Heapify)' 연산을 수행하여 다시 최대 힙 속성을 만족시킵니다. > 4. 힙의 크기가 1이 될 때까지 1~3번 과정을 반복합니다.
- 결과 : 2단계가 끝나면, 배열의 뒤쪽부터 가장 큰 값이 차례대로 채워져 전체 배열이 오름차순으로 정렬됩니다.
👍 힙 정렬의 장점과 단점
- 장점 (Advantages)
> * 보장된 성능 : 최선, 평균, 최악의 경우 모두 항상 O(n log n)의 시간 복잡도를 보장합니다. > * 제자리 정렬 (In-place Sort) : 정렬 과정에서 추가적인 메모리 공간을 거의 필요로 하지 않습니다.
- 단점 (Disadvantages)
> * 불안정 정렬 (Unstable Sort) : 정렬 과정에서 동일한 값을 가지는 원소들의 상대적인 순서가 바뀔 수 있습니다. > * 평균 속도 : 퀵 정렬에 비해 실제 실행 시간이 느린 편입니다. (참조의 지역성(locality of reference) 원리에 불리하여 캐시 효율이 떨어짐)
💡 개발자 핵심 Point
- 힙 정렬은 보장된 O(n log n) 성능과 제자리 정렬이라는 두 가지 장점을 모두 갖춘 드문 알고리즘입니다.
- 퀵 정렬(Quick Sort)과의 비교
> * 퀵 정렬은 평균적으로 더 빠르지만 최악의 경우 O(n²)의 위험이 있습니다. > * 힙 정렬은 퀵 정렬보다 평균적으로 느리지만 항상 O(n log n)을 보장합니다.
- 인트로소트(Introsort) : 퀵 정렬의 최악의 경우를 방지하기 위해, 퀵 정렬의 재귀 깊이가 일정 수준 이상으로 깊어지면 힙 정렬로 전환하는 방식입니다. 많은 언어의 표준 라이브러리에서 사용됩니다.
- 힙 정렬은 우선순위 큐(Priority Queue)를 이용한 정렬 방식이라고도 볼 수 있습니다.
