힙정렬 (Heap Sort)
쉽게 풀면
숫자 카드 더미를 정렬한다고 해봅시다. 힙정렬은 먼저 카드 더미를 "가장 큰 카드가 항상 맨 위에 오는" 특별한 트리 모양(최대 힙)으로 재배치합니다. 그 다음 맨 위 카드(가장 큰 값)를 뽑아 배열의 맨 뒤에 놓고, 남은 카드들로 다시 힙 모양을 만드는 과정을 반복합니다. 이렇게 "가장 큰 값 뽑기 → 남은 것으로 힙 재구성"을 계속하면 결국 작은 값부터 큰 값까지 순서대로 늘어선 배열이 완성됩니다. 힙을 만드는 데 걸리는 시간과 값을 하나씩 꺼내는 데 걸리는 시간을 합쳐도 전체 과정은 O(n log n)이며, 병합정렬처럼 별도의 큰 배열을 추가로 만들 필요 없이 원래 배열 안에서 자리를 바꿔가며 정렬을 끝낼 수 있다는 점이 특징입니다.
왜 중요한가
힙정렬은 항상 O(n log n)의 최악 시간복잡도를 보장하면서도 추가 메모리를 거의 필요로 하지 않는 제자리 정렬이라는 점 때문에, 메모리 제약이 큰 임베디드 시스템이나 대용량 데이터 처리 연구에서 다른 정렬 알고리즘과 비교 대상으로 자주 등장합니다. 퀵정렬처럼 평균적으로는 빠르지만 최악의 경우 성능이 나빠질 수 있는 알고리즘의 대안으로, 안정적인 성능이 요구되는 실시간 시스템이나 임베디드 환경을 다루는 논문에서 언급되는 경우가 많습니다.
논문에서는 이렇게 쓰입니다
이 문장은 "데이터 양이 많아 메모리를 아껴야 하는 상황이라, 추가 공간이 필요한 정렬 방식 대신 제자리에서 정렬이 가능한 힙정렬을 선택했다"는 뜻입니다.
메모리와 실행 안정성이 중요한 임베디드 소프트웨어 연구에서, 힙정렬의 예측 가능한 성능이 장점으로 강조되는 사례다.
실시간 시스템 분야에서 평균 속도보다 성능의 예측 가능성을 우선시하는 상황을 보여주는 예시다.
조금 더 깊게 보면
힙정렬은 크게 두 단계로 진행됩니다. 먼저 주어진 배열 전체를 최대 힙(또는 최소 힙) 형태로 재배치하는 힙 구성 단계를 거치고, 이후 루트에 위치한 최댓값을 배열 끝으로 옮기고 남은 원소들로 힙 속성을 다시 맞추는 과정을 반복하는 정렬 단계로 이어집니다. 이 두 단계 모두 별도의 배열을 새로 만들지 않고 원래 배열 안에서 원소 위치만 바꾸기 때문에 공간복잡도가 O(1)에 가깝다는 점이 실용적인 장점으로 꼽힙니다. 다만 캐시 지역성 측면에서는 배열을 순차적으로 접근하는 퀵정렬이나 병합정렬에 비해 불리한 경우가 많아, 실제 성능은 이론적 시간복잡도만으로 단정하기 어렵다는 점도 함께 논의됩니다.
주의할 점
힙정렬은 추가 메모리 없이 원래 배열 안에서 정렬을 끝낼 수 있다는 장점이 있지만, 같은 값을 가진 원소들의 원래 순서가 뒤바뀔 수 있는 불안정 정렬(unstable sort)입니다. 힙을 구성하고 값을 꺼내는 과정 자체는 우선순위 큐와 힙 구조의 성질을 그대로 활용한 것이므로, 힙 자료구조의 동작 원리를 먼저 이해하면 힙정렬의 각 단계가 훨씬 명확하게 와닿습니다.