힙 정렬(Heap Sort)

🟩 '힙' 자료구조의 장점을 활용한 정렬

최대힙 트리나 최소힙 트리를 구성해 정렬을 하는 방법

내림차순 정렬을 위해서는 최대힙 (루트가 가장 큼)을 구성하고

오름차순 정렬을 위해서는 최소힙 (루트가 가장 작음)을 구성한다.

 

🟩 과정

1. n개의 노드에 대한 완전 이진 트리 구성

2. 최대힙 구성

3. 가장 큰 수(루트에 위치)를 가장 끝의 노드와 교환

4. 2와 3을 반복

🟩 시간복잡도

힙과 동일하게 O(nlogn)

최대힙으로 만드는 과정 O(logn), n개의 원소를 다 정렬할 때까지 반복 하므로

 

🟩 특징

제자리 정렬 (추가적인 공간이 필요하지 않음) 👉 메모리 측면에서 몹시 효율적 cf. 합병정렬

항상 시간복잡도 O(nlogn)을 보장

하지만 단순히 속도만 가지고 비교하면 퀵 정렬이 평균적으로 빠르기 때문에 힙 정렬이 많이 사용되지는 않음

 

🚀 퀵 정렬과의 비교

둘 다 같은 nlogn이지만, 컴퓨터의 하드웨어 구조상 퀵 정렬이 실제로 더 빠르다.

이유는 퀵정렬은 데이터를 피벗을 기준으로 좌우로 나누어 정렬하는 방식으로, 최선의 경우 nlogn, 최악의 경우 n^2이다. 반면, 힙정렬의 경우 힙 트리 구조를 유지하면서 정렬을 진행하기 때문에 모든 경우에 nlogn의 시간 복잡도를 보장한다.

그러나 퀵 정렬이 대개 원소들끼리 근접한 메모리 영역에 붙어 있는 배열을 사용하기 때문에 캐시 효율성 측면에서 더 빠르다. 반면 힙 정렬의 경우, 캐시 효율성이 떨어진다는 문제와 일반적으로 포인터 연산을 많이 사용하여 발생하는 오버헤드도 무시할 수 없다.