no_mkd
1. 힙 정렬의 장단점(pros and cons)
(알고리즘의 가치를 파악하기 위해 장단점을 먼저 간단히 살펴보겠습니다. 좋지 않은 알고리즘을 이해하느라 시간을 낭비할 필요는 없으니까요.)
장점:
- 힙 정렬의 효율은 퀵 정렬, 병합 정렬과 마찬가지로 비교 기반 정렬 알고리즘의 한계치에 도달해 있습니다(시간 복잡도 O(nlogn)).
- 효율성 외에 가장 큰 특징은 O(1)의 보조 공간만 필요하다는 점입니다. 최고 효율과 최소 공간을 동시에 만족하는 유일한 알고리즘입니다.
- 힙 정렬의 효율은 상대적으로 안정적입니다. 퀵 정렬이 최악의 경우 O(n^2)으로 떨어지는 것과 달리, 정렬할 데이터의 상태와 관계없이 항상 O(nlogn)을 유지합니다. (여기서의 안정성은 평균 시간 복잡도가 최악의 경우와 같다는 의미이지, 정렬의 '안정성(Stable)'을 뜻하는 것은 아닙니다. 힙 정렬 자체는 불안정 정렬입니다.)
단점: (위의 장점만 보면 완벽해 보이는데, 왜 실제 내부 정렬에서 힙 정렬보다 퀵 정렬이 더 많이 쓰일까요?)
- 가장 크고 유일한 단점은 '힙 유지 보수' 문제입니다. 실제 환경의 데이터는 빈번하게 변하는데, 데이터가 업데이트(추가, 삭제, 수정)될 때마다 힙의 특성을 유지하기 위해 매번 재구성 과정을 거쳐야 합니다. 이는 대부분의 경우 불필요한 작업이 될 수 있습니다. (그래서 퀵 정렬이 실무의 강자가 되었고, 힙 정렬은 알고리즘 서적에서만 빛을 발하게 되었습니다. 물론 데이터 업데이트가 잦지 않은 상황이라면 힙 정렬이 더 좋을 수 있습니다.)
2. 내부 원리
먼저 힙 정렬의 단계를 알아야 합니다:
- 초기 힙 구축: 주어진 수열을 바탕으로 첫 번째 최대 힙(Max-heap) 또는 최소 힙(Min-heap)을 만듭니다. (힙이 무엇인지는 생략하겠습니다. 짚더미 쌓아 놓은 모양을 생각하시면 됩니다.)
- 루트와 마지막 원소 교환 후 꼬리 자르기: 루트 원소를 마지막 원소와 바꾸고, 마지막 원소를 제외한 나머지 부분으로 다시 힙을 재구성합니다.
- 2단계 반복: 모든 원소가 처리될 때까지 반복하면 정렬이 완료됩니다.
최소 힙으로 정렬하면 내림차순(또는 비오름차순) 결과가 나오고, 최대 힙으로 정렬하면 오름차순 결과가 나옵니다.
얼핏 생각하면 반대인 것 같지만(최소 힙은 가장 작은 게 맨 위인데 왜 내림차순?), 아래 그림들을 보면 이해가 가실 겁니다:
정렬할 수열이 a[] = {7, 1, 6, 5, 3, 2, 4}이고 최대 힙 방식으로 정렬한다고 가정해 봅시다.
1단계 (초기 힙 구축):
{7, 5, 6, 1, 3, 2, 4}는 이제 최대 힙 조건을 만족하므로 1단계가 끝났습니다.
2단계 (루트-마지막 교환, 꼬리 자르기 및 재구성):
3단계 (모든 원소의 꼬리가 잘릴 때까지 반복):
그림은 생략하겠습니다. (그리기가 너무 힘드네요...) 2단계까지만 이해하셨다면 나머지는 직접 그려보며 충분히 파악하실 수 있을 것입니다.
결국 핵심은 '꼬리 자르기'입니다. 안타깝게도 많은 자료에서 이 부분을 명확히 언급하지 않지만, 이보다 더 적절한 설명이 있을까요?
3. 구현 세부 사항
원리 설명의 그림에서 세부 구현 사항을 어느 정도 보여드렸으므로, 여기서는 코드 구현에 집중하겠습니다.
먼저 직접 작성해 본 최대 힙 방식의 구현입니다:
#include<stdio.h>//构造大根堆（让a[m]到a[n]满足大根堆） void HeapAdjust(int a[], int m, int n){ int temp; int max; int lc;//左孩子 int rc;//右孩子
while(1){ //获取a[m]的左右孩子 lc = 2 * m + 1; rc = 2 * m + 2; //比较a[m]的左右孩子，max记录较大者的下标 if(lc >= n){ break;//不存在左孩子则跳出 } if(rc >= n){ max = lc;//不存在右孩子则最大孩子为左孩子 } else{ max = a[lc] > a[rc] ? lc : rc;//左右孩子都存在则找出最大孩子的下标 } //判断并调整（交换） if(a[m] >= a[max]){//父亲比左右孩子都大，不需要调整，直接跳出 break; } else{//否则把小父亲往下换 temp = a[m]; a[m] = a[max]; a[max] = temp; //准备下一次循环，注意力移动到孩子身上，因为交换之后以孩子为根的子树可能不满足大根堆 m = max; } }}
void HeapSort(int a[], int n){ int i,j; int temp;
//自下而上构造小根堆（初始堆） for(i = n / 2 - 1;i >= 0;i--){//a[n/2 - 1]恰好是最后一个非叶子节点（叶子节点已经满足小根堆，只需要调整所有的非叶子节点），一点小小的优化 HeapAdjust(a, i, n); } printf("初始堆: "); for(i = 0;i < n;i++){ printf("%d ", a[i]); } printf("\n"); for(i = n - 1;i > 0;i--){ //首尾交换，断掉尾巴 temp = a[i]; a[i] = a[0]; a[0] = temp; //断尾后的部分重新调整 HeapAdjust(a, 0, i); /* printf("第%d次（i - 1 = %d）: ", n - i, i - 1); for(j = 0;j < n;j++){ printf("%d ", a[j]); } printf("\n"); */ }}
main(){ //int a[] = {5, 6, 3, 4, 1, 2, 7}; //int a[] = {1, 2, 3, 4, 5, 6, 7}; //int a[] = {7, 6, 5, 4, 3, 2, 1}; int a[] = {7, 1, 6, 5, 3, 2, 4}; int m, n; int i;
m = 0; n = sizeof(a) / sizeof(int); //HeapAdjust(a, m, n); HeapSort(a, n); printf("结果: "); for(i = 0;i < n;i++){ printf("%d ", a[i]); } printf("\n");}
P.S. 스스로 한 단계씩 생각하며 작성한 코드라 주석이 매우 상세합니다. 코드를 직접 보시면 이해하기 어렵지 않을 것입니다.
다음은 일반적인 서적에서 다루는 최대 힙 방식의 구현입니다:
#include<stdio.h>void HeapAdjust(int a[], int m, int n){ int i; int t = a[m];
for(i = 2 * m + 1;i <= n;i = 2 * i + 1){ if(i < n && a[i + 1] > a[i])++i; if(t >= a[i])break; //把空缺位置往下放 a[m] = a[i]; m = i; } a[m] = t;//只做一次交换，步骤上的优化}
void HeapSort(int a[], int n){ int i; int t;
//自下而上构造大根堆 for(i = n / 2 - 1;i >= 0;--i){ HeapAdjust(a, i, n - 1); } printf("初始堆: "); for(i = 0;i < n;i++){ printf("%d ", a[i]); } printf("\n"); for(i = n - 1;i > 0;i--){ //首尾交换，断掉尾巴 t = a[i]; a[i] = a[0]; a[0] = t; //对断尾后的部分重新建堆 HeapAdjust(a, 0, i - 1); }}
main(){ //int a[] = {5, 6, 3, 4, 1, 2, 7}; //int a[] = {1, 2, 3, 4, 5, 6, 7}; //int a[] = {7, 6, 5, 4, 3, 2, 1}; int a[] = {7, 1, 6, 5, 3, 2, 4}; int m, n; int i;
m = 0; n = sizeof(a) / sizeof(int); //HeapAdjust(a, m, n); HeapSort(a, n); printf("结果: "); for(i = 0;i < n;i++){ printf("%d ", a[i]); } printf("\n");}
P.S. 서적의 코드는 훨씬 짧습니다. 단순한 분량 축소가 아니라 단계별 최적화가 이루어져 있으며, 미세한 차이는 주석에 적어 두었습니다. 하지만 이런 최적화가 가독성을 떨어뜨리는 면이 있어 알고리즘 책을 잡았다가 다시 내려놓게 만들기도 하죠... (실무에서는 서적의 효율성을 유지하면서 가독성을 높이는 방향으로 코드를 다듬는 것이 좋습니다.)
마지막으로 서적의 알고리즘을 연구한 후 최적화 기법을 결합하여 작성한 최소 힙 방식의 구현입니다 (인터넷 자료는 대부분 최대 힙 방식이므로, 지루함을 피하기 위해 원리는 같지만 다르게 작성해 보았습니다):
#include<stdio.h>//构造小根堆（让a[m]到a[n]满足小根堆） void HeapAdjust(int a[], int m, int n){ int i; int t = a[m]; int temp;
for(i = 2 * m + 1;i <= n;i = 2 * i + 1){ //a[m]的左右孩子比较，i记录较小者的下标 if(i < n && a[i + 1] < a[i]){ i = i + 1; } if(t <= a[i]){ break; } else{//把空缺位置往下换 //把较小者换上去 temp = a[m]; a[m] = a[i]; a[i] = temp; //准备下一次循环 m = i; } }}
void HeapSort(int a[], int n){ int i, j; int temp;
//自下而上构造小根堆（初始堆） for(i = n / 2 - 1;i >= 0;i--){//a[n/2 - 1]恰好是最后一个非叶子节点（叶子节点已经满足小根堆，只需要调整所有的非叶子节点），一点小小的优化 HeapAdjust(a, i, n); } printf("初始堆: "); for(i = 0;i < n;i++){ printf("%d ", a[i]); } printf("\n"); //把每个元素都调整到应该去的位置 for(i = n - 1; i > 0;i--){ //首尾交换 temp = a[i]; a[i] = a[0]; a[0] = temp; //断尾后剩余部分重新调整 HeapAdjust(a, 0, i - 1); }}
main(){ //int a[] = {7, 6, 5, 4, 3, 2, 1}; //int a[] = {1, 5, 6, 4, 3, 2, 7}; int a[] = {1, 2, 3, 4, 5, 6, 7}; int m, n; int i;
m = 0; n = sizeof(a) / sizeof(int); //HeapAdjust(a, m, n); HeapSort(a, n); printf("结果: "); for(i = 0;i < n;i++){ printf("%d ", a[i]); } printf("\n");}
P.S. 주석은 여전히 상세합니다. 코드를 참조해 주세요.
4. 요약
힙 정렬의 단계는 아주 명료합니다: 힙 빌드 -> 루트-마지막 교환 및 꼬리 자르기 -> 모든 원소의 꼬리가 잘릴 때까지 반복
이보다 더 명확한 설명이 있을까요?
우리는 이제 유용한 정렬 알고리즘 몇 가지를 익혔습니다:
실제 응용에서는 어떻게 선택해야 할까요? 다음과 같은 기준이 있습니다:
- n이 작을 때: 삽입 정렬이나 단순 선택 정렬을 사용합니다. 삽입 정렬이 선택 정렬보다 데이터 이동이 많으므로, 데이터 자체의 크기가 클 때는 선택 정렬이 더 유리합니다.
- 이미 어느 정도 정렬된 상태일 때: 삽입 정렬이나 버블 정렬이 효율적입니다.
- n이 클 때: 시간 복잡도가 가장 낮은 퀵 정렬, 힙 정렬, 병합 정렬 중 하나를 선택합니다.
-
- 데이터가 무작위로 분포되어 있다면 퀵 정렬이 가장 빠릅니다(하드웨어 최적화와 관련이 있음).
- 보조 공간을 최소화해야 한다면 힙 정렬이 최선이며, 퀵 정렬과 달리 최악의 경우에도 성능 저하가 없습니다.
- 정렬의 안정성(Stable)이 중요하다면 병합 정렬을 사용합니다. 삽입 정렬과 병합 정렬을 결합하여(작은 조각들을 삽입 정렬로 먼저 정렬한 뒤 병합) 안정성을 유지하면서 속도를 높일 수도 있습니다.
참고: '꼬리 자르기'라는 비유는 선배 개발자의 포스팅을 참고했습니다. 감사의 뜻을 전합니다.
아직 댓글이 없습니다