힙 정렬 (Heap Sort)

힙 정렬(Heap Sort)은 선택 정렬(Selection Sort)의 변형으로, 최대 힙(Max Heap)을 이용한 정렬 알고리즘 입니다.

 

힙 정렬의 동작 과정은 다음과 같습니다.

1. 주어진 배열을 최대 힙으로 구성합니다.
2. 최대 힙에서 가장 큰 값을 꺼내어 배열의 마지막 요소와 교환합니다.
3. 마지막 요소를 제외한 나머지 배열을 다시 최대 힙으로 구성합니다.
4. 반복하여 정렬이 완료될 때까지 2~3번 과정을 수행합니다.

아래는 힙 정렬의 동작 과정을 나타낸 그림입니다.

출처: https://en.wikipedia.org/wiki/Heapsort#Algorithm

 

힙 정렬의 시간 복잡도는 항상 O(nlogn)이며, 특히 입력 배열의 크기와 상관없이 항상 같은 시간복잡도를 보장합니다.

 

그러나 최악의 경우에는 상수항이 크기 때문에, 실제로는 퀵 정렬(Quick Sort)이나 병합 정렬(Merge Sort)보다 느릴 수 있습니다.

 

또한, 힙 정렬은 선택정렬(Selection Sort)의 특징을 그대로 가지고 있기 때문에, 불안정 정렬(Unstable Sort)입니다.