힙 정렬(Heap Sort) - 정의 / 예시 코드

 

힙 정렬(Heap Sort)은 힙 자료구조를 기반으로 동작하는 정렬 알고리즘입니다. 최대 힙(Max Heap) 또는 최소 힙(Min Heap)을 구성하여 배열을 정렬하는 방식으로 동작합니다. 힙 정렬은 주로 배열 기반의 힙 자료구조를 사용하여 구현됩니다.

아래는 힙 정렬의 동작 과정을 단계별로 설명한 것입니다.

1. 주어진 배열을 최대 힙 또는 최소 힙으로 구성합니다. 이 단계를 힙 구성(Heapify) 단계라고 합니다. 최대 힙을 구성하는 경우, 부모 노드는 항상 자식 노드보다 큰 값을 가지며, 최소 힙을 구성하는 경우에는 그 반대입니다.

 

2. 힙에서 최상단에 있는 노드(최대 힙의 경우 최댓값, 최소 힙의 경우 최솟값)를 꺼내어 배열의 마지막 위치로 이동시킵니다. 이 단계를 반복적으로 수행하면, 배열은 점차 정렬된 상태로 변경됩니다.

 

3. 배열에서 꺼낸 노드를 힙의 제약 조건을 유지하면서 다시 힙에 삽입합니다. 이 단계를 힙 복원(Heapify) 단계라고 합니다. 최대 힙의 경우 새로 삽입한 값이 부모 노드보다 작으면 값을 노드와 교체하고, 최소 힙의 경우에는 반대로 처리합니다.

 

4. 위의 단계를 배열의 첫 번째 원소까지 반복합니다.

 

반응형

 

힙 정렬은 힙의 구성 및 복원 단계에서 O(log n)의 시간이 소요되며, 전체 배열을 정렬하는 데에는 총 O(n log n)의 시간이 소요됩니다. 이러한 특성으로 인해 힙 정렬의 시간 복잡도는 항상 O(n log n)입니다. 또한, 힙 정렬은 안정적인 정렬 알고리즘은 아니지만, 제자리 정렬(In-place Sort)이 가능하다는 장점이 있습니다.

 

아래는 C++로 구현된 힙 정렬의 예시 코드입니다.

 

 

위의 예시 코드를 실행하면, 배열 {64, 25, 12, 22, 11}가 오름차순으로 정렬되어 {11, 12, 22, 25, 64}가 출력됩니다.