5. 정렬된 자리는 힙에서 빼낸다
해설글
작성 · 3분 읽기 · 조회수 —수정
기초 개념과 예제를 보강하고 시리즈 흐름을 연결
n을 저장하고 줄이고 되돌리는 메모
힙 정렬은 최대 힙의 루트가 현재 최댓값이라는 성질을 사용한다. 먼저 배열 전체를 최대 힙으로 만들고, 루트와 힙의 마지막 원소를 바꾼다. 최댓값은 배열 끝의 최종 위치에 도착하고, 남은 앞부분만 다시 최대 힙으로 고친다.
하나의 배열
[ 아직 힙으로 다룰 구간 | 이미 정렬된 구간 ]
^ 경계가 왼쪽으로 이동
down-heap은 전체 배열이 아니라 경계 왼쪽만 봐야 한다. 정렬 완료 구간을 다시 힙에 넣으면 확정한 최댓값이 앞으로 돌아올 수 있다.
힙 정렬 노트에는 전역 변수 n을 다루는 순서가 거듭 적혀 있다.
save 변수를 통해 n값 저장 후
swap([1], [n]), n– 하여 큰수를 맨 뒤로 보내는 작업 후 연산범위 축소
DownHeap(1)을 해야한다
다른 메모에는 “전역변수 n 선언 시 다른 함수 안에서 종속변수로 n을 사용하지 말자”는 주의도 있다. 원본 코드에서 n은 입력 배열의 전체 길이인 동시에 아직 힙으로 취급할 구간의 끝이다. 정렬이 진행되면 두 값은 달라진다.
최대 힙의 루트에는 현재 구간의 최댓값이 있다. 루트와 힙의 마지막 값을 바꾸면 최댓값은 최종 위치에 도착한다. 그다음 DownHeap은 방금 확정한 자리를 보지 않아야 한다. 그래서 swap 뒤의 유효 크기는 size가 아니라 정확히 size - 1이다.
for (int size = n; size >= 2; size--) {
swap(&a[1], &a[size]);
down_heap(a, size - 1, 1);
}
down_heap(a, size, 1)로 호출하면 끝에 둔 최댓값까지 자식 후보로 다시 들어온다. 루트보다 큰 그 값이 앞쪽으로 이동할 수 있어 “이 자리는 정렬 완료”라는 전제가 사라진다. size - 1은 단순한 인덱스 조정이 아니라 문제에서 답 하나를 제외하는 연산이다.
배열 하나에서 움직이는 경계
이번에는 [4, 1, 3, 2]를 따라가 보자. 상향식으로 최대 힙을 만들면 [4, 2, 3, 1]이 된다. 보기 쉽게 값만 적었지만 구현은 1번 인덱스부터 사용한다.
| 반복 | swap 직후 | DownHeap 뒤 | 힙 구간 | 확정 구간 |
|---|---|---|---|---|
| 시작 | - | 4 2 3 1 |
4 2 3 1 |
없음 |
| size=4 | 1 2 3 4 |
3 2 1 4 |
3 2 1 |
4 |
| size=3 | 1 2 3 4 |
2 1 3 4 |
2 1 |
3 4 |
| size=2 | 1 2 3 4 |
그대로 | 1 |
2 3 4 |
매 반복이 끝날 때 왼쪽 1..size-1은 다시 최대 힙이고 오른쪽 size..n은 오름차순으로 확정된다. 왼쪽의 모든 값은 오른쪽의 모든 값보다 작거나 같다. 이 경계가 한 칸씩 왼쪽으로 이동하며 정렬이 완성된다.
원본은 전역 n을 감소시키고 마지막에 originalN으로 복원한다. 복원하지 않으면 정렬 뒤 n=1이라 출력 함수가 첫 값만 출력한다. 이번 재현 코드에서는 전체 길이와 현재 heap_size를 서로 다른 값으로 전달했다. 원본의 방법을 부정한 것이 아니라 한 변수에 겹친 두 의미를 드러낸 것이다.
제자리와 안정성의 구분
힙 정렬의 1기는 상향식 힙 생성 O(n), 2기는 거의 n번의 swap과 O(log n) DownHeap이므로 O(n log n)이다. 반복형 구현은 입력 배열 외에 몇 개의 정수만 써 제자리 정렬이 된다.
그렇다고 안정 정렬은 아니다. 같은 값에 원래 위치를 붙여 4a, 4b로 구분하면 루트와 끝의 먼 swap 때문에 4b가 4a보다 앞설 수 있다. 제자리는 추가 저장 공간에 관한 성질이고 안정성은 같은 키의 상대 순서에 관한 성질이다.
이번에 작성한 재현 코드는 빈 배열, 한 원소, 중복 값, 역순 값을 표준 qsort와 대조한다. AddressSanitizer와 UndefinedBehaviorSanitizer를 켠 실행에서 모든 검사가 통과했다. 이는 이번 코드의 값 정렬과 경계를 확인한 결과이며 과거 노트에 없던 실행이다.
노트의 n--를 외우는 데서 멈추면 전역 변수 관리 규칙으로만 보인다. 매 반복에서 힙과 확정 구간을 나누어 보면 의미가 달라진다. 정렬된 자리는 다시 비교할 후보가 아니므로 힙에서 빼낸다.
참고한 기록과 코드
- 개인 노트 「4주차 - 힙정렬」, 2025-10-20
- 개인 노트 「c언어 암기사항」, 2025-12-15
Week4(Heap_Sort)/0922-1.c