힙 정렬(Heap Sort) 제자리 정렬(In-place) 구현 완벽정리

데이터를 정렬하는 수많은 알고리즘 중, 힙 정렬(Heap Sort)은 O(N log N)이라는 아주 빠르고 훌륭한 시간 복잡도를 100% 확정적으로 보장하면서도, 병합 정렬(Merge Sort)처럼 배열을 복사하기 위한 추가적인 메모리 공간을 전혀 요구하지 않는 극강의 효율을 자랑합니다. 원본 배열 그 자체만을 도마 위에 올려두고 요리하듯 뚝딱 정렬을 마쳐버리는 이러한 특성을 '제자리 정렬(In-place Sort)'이라고 부릅니다. 퀵 정렬(Quick Sort)이 최악의 경우 O(N^2)으로 느려질 위험을 안고 있는 반면, 힙 정렬은 어떠한 악의적인 데이터가 들어와도 흔들림 없이 안정적인 성능을 뽑아냅니다. 오늘은 1차원 배열을 가상의 완전 이진 트리로 매핑하는 수학적 마법과, 가장 큰 값을 맨 뒤로 차곡차곡 쌓아 올리는 힙 정렬의 완벽한 제자리 정렬 구현 과정을 낱낱이 해부해 보겠습니다.

1. 힙(Heap)과 배열의 기막힌 수학적 매핑 (Mapping)

힙 정렬이 추가 메모리(객체나 포인터)를 쓰지 않는 이유는, 1차원 배열 자체를 '완전 이진 트리(Complete Binary Tree)'로 취급해 버리기 때문입니다. 배열의 인덱스를 가지고 아주 간단한 곱셈과 나눗셈만 하면 특정 노드의 부모와 자식 위치를 0.001초 만에 바로 찾아갈 수 있습니다.

1-1. 인덱스 점프 공식 (배열 인덱스가 0부터 시작할 때)

배열 arr[i]에 있는 원소를 트리의 한 노드라고 생각한다면, 이 노드의 가족들은 항상 정해진 규칙의 배열 칸에 살고 있습니다.

왼쪽 자식의 위치: 2 * i + 1
오른쪽 자식의 위치: 2 * i + 2
부모의 위치: (i - 1) / 2 (소수점 버림)

이 단순한 산술 공식 덕분에, 힙 정렬은 노드 객체를 생성하거나 메모리 주소를 할당받는 오버헤드 없이 배열 안에서 미친 듯이 점프하며 데이터를 비교할 수 있습니다.

2. 1단계: 배열을 최대 힙(Max Heap)으로 개조하기 (Heapify)

정렬을 시작하려면 먼저 뒤죽박죽인 일반 배열을 '부모 노드가 자식 노드보다 항상 크거나 같은' 최대 힙(Max Heap) 상태로 뼈대를 뜯어고쳐야 합니다. 이 과정을 Heapify라고 부릅니다.

2-1. 바닥에서부터 끌어올리는 O(N)의 마법

배열의 마지막 요소부터 처음까지 역순으로 돌면서 구조를 잡는 것이 아니라, '자식을 가지고 있는 마지막 부모 노드'부터 시작하여 루트 노드(인덱스 0)까지 역순으로 차례대로 Heapify 함수를 호출합니다.


// 서브 트리를 최대 힙 구조로 만드는 재귀/반복 함수 (Java)
void heapify(int[] arr, int size, int i) {
    int largest = i; // 일단 내가 제일 크다고 가정
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    // 왼쪽 자식이 나보다 크면 갱신
    if (left < size && arr[left] > arr[largest]) largest = left;
    // 오른쪽 자식이 제일 크면 갱신
    if (right < size && arr[right] > arr[largest]) largest = right;

    // 만약 자식이 나보다 크다면, 자리를 바꾸고 바뀐 자식 쪽으로 계속 타고 내려감
    if (largest != i) {
        swap(arr, i, largest);
        heapify(arr, size, largest);
    }
}

이렇게 밑바닥 부모부터 위로 올라가며 트리를 다지면, 놀랍게도 전체 배열을 힙 구조로 만드는 데 걸리는 시간 복잡도가 O(N log N)이 아니라 O(N)으로 획기적으로 압축됩니다.

3. 2단계: 정렬의 완성, 루트 뽑기와 트리 재구성

이제 배열은 거대한 최대 힙이 되었습니다. 최대 힙의 가장 위대한 특성은 "배열의 0번 인덱스(루트 노드)에는 무조건 배열 전체에서 가장 거대한 최댓값이 들어있다"는 것입니다. 이 성질을 이용해 제자리 정렬(In-place)을 시작합니다.

3-1. 꼬리 자르기와 뒷부분 채우기

배열의 맨 앞 arr[0](가장 큰 값)과 배열의 맨 끝 요소를 스왑(Swap)하여 자리를 맞바꿉니다. 이제 배열의 가장 큰 값은 맨 뒤에 안전하게 고정되었습니다.
가장 큰 값이 뒤로 갔으므로, 힙의 취급 사이즈(Size)를 1칸 줄입니다. (맨 뒤의 칸은 이제 정렬이 끝난 '불가침 영역'이 됩니다.)
맨 끝에 있던 엉뚱하고 작은 값이 루트 arr[0]으로 올라왔으므로, 힙의 규칙이 깨졌습니다. 사이즈가 1 줄어든 힙을 대상으로 0번 인덱스부터 다시 heapify()를 1회 실행하여 최댓값을 다시 꼭대기로 끌어올립니다. 이 과정은 O(log N)이 소요됩니다.
힙의 사이즈가 1이 될 때까지 이 스왑과 갱신 과정을 계속 무한 반복합니다.

모든 반복이 끝나면, 배열의 뒷부분부터 가장 큰 값, 두 번째로 큰 값, 세 번째로 큰 값이 차곡차곡 예쁘게 쌓이면서 완벽한 오름차순 정렬 배열이 완성됩니다. 추가 배열 없이 원본 배열의 스왑만으로 O(N log N)을 달성한 컴퓨터 공학의 걸작입니다.

[핵심 요약]
1. 힙 정렬(Heap Sort)은 별도의 추가 배열 없이 원본 배열 자체를 이진 트리로 취급하여 메모리 낭비를 없앤 제자리 정렬(In-place Sort)입니다.
2. 인덱스 곱셈(2i+1, 2i+2)을 활용해 일반 배열을 O(N)의 속도로 최대 힙(Max Heap) 구조로 개조하는 것이 1단계입니다.
3. 최댓값이 모이는 루트 노드(0번 인덱스)를 배열의 맨 끝 요소와 스왑(Swap)하고 힙의 사이즈를 줄여나가며 재정렬하는 과정을 반복하여 O(N log N)의 확정적인 정렬 속도를 냅니다.

코드 아카이브