히프정렬 (heap sort)
합병 정렬방식은 비록 최악의 경우 연산 시간과 평균 연산 시간 모두 O(nlogn)이지만, 정렬할 레코드 수에 비례하여 저장 공간이 추가로 필요하다.
히프 정렬(heap sort)은 일정한 양의 저장 공간만 추가적으로 필요한 동시에, 최악의 경우 평균 연산 시간이 O(n log n)이다. 하지만, 히프 정렬은 합병 정렬보다 약간 느리다.
히프 정렬의 핵심 알로리즘은 이름처럼 히프를 사용한다. 그중에서도 최대 히프 구조를 이용한다.
따라서, 최대 히프가 되도록 레코드를 재조정 후 루트를 하나씩 빼내면서 정렬을 하는 기법이다.
알로리즘을 정리하면,
1. 최대 히프 생성
2. 히프의 첫 번째 와 마지막 레코드 스와핑
2. 히프의 첫 번째 와 마지막 레코드 스와핑
3. 히프 크기 감소 및 재조정
4. n-1 반복
최대 히프 생성 과정
최대 히프를 구하는 adjust 함수
void adjust(element a[]], int root, int n)
{
element temp;
temp = a[root];
rootkey = a[root].key;
child = 2 * root; //왼쪽 자식
while (child <= n) {
if ((child < n) && (a[child].key < a[child + 1].key)
child++;
if (rootkey > a[child].key) // 루트와 최대값 비교
break;
else { // 부모 이동
a[child / 2] = a[child];
child *= 2;
}
}
a[child / 2] = temp;
}최대 히프로 구성 했으면 이제 root에서 하나씩 빼면서 정렬를 해주고
다시 최대 히프로 재구성하여 이 작업을 반복해준다.
heap sort 함수
void heapsort(element a[], int n)
{
int i, j;
element tmep;
for (i = n / 2; i > 0; i--)
adjust(a, i, n); // max heap 구성 부분
for (i = n - 1; i > 0; i--)
{
SWAP(a[1], a[i + 1], temp); // 루트 교환 부분
adjust(a, 1, i);
}
}
실습 예제
주어진 데이터를 읽어 Heap Sort를 수행하라
1) 입력 데이터는 다음과 같은 형식을 가지는 파일(input.txt)로부터 입력받는다.
N R 1,1 R 1,2
R 2,1 R 2,2
…
R N,1 R N,2
N: Record의 갯수이며, N≤1000라 가정한다.. Ri, j 는 정수이며, i번째 Record의 j번 field를 나타낸다.
2) 주어진 입력에 대해 첫번째 Key (K 1 )에 대해 초기 힙(max heap)을 구성한다.
3) 구성된 Max heap을 이용하여 첫번째 Key(K 1 )에 대해 Heap Sort를 수행하여 오름차순 정렬을 한다.
4) 두번째 Key(K 2 )에 대해 2), 3)을 수행한다.
입력값
input.txt
8
-1 5
31 4
95 -9
82 3
1984 124
-78 -42
0 -154
525 195
코드
/*
Description : Heap Sort 구현
*/
#include <stdio.h>
#include <stdlib.h>
#include <Windows.h>
#define SWAP(x,y,t) ((t)=(x),(x)=(y),(y)=(t))
#define KEY1 1
#define KEY2 2
typedef struct element
{
int key1;
int key2;
}element;
void open();
void Init(element[]);
void Print(element[]);
void heapSort(element a[], int n, int);
void adjust(element a[], int root, int n, int);
void COLOR(int);
element *matric;
element* sort;
int N;
int main(void)
{
open();
sort = (element*)malloc(sizeof(element) * (N + 1));
Init(sort); //초기화
COLOR(14);
printf("====Key: K1====\n");
COLOR(15);
heapSort(sort, N, KEY1);
printf("\n");
Init(sort); //초기화
COLOR(14);
printf("====Key: K2====\n");
COLOR(15);
heapSort(sort, N, KEY2);
return 0;
}
void open()
{
FILE *fp = fopen("input.txt", "r");
fscanf(fp, "%d", &N);
matric = (element*)malloc(sizeof(element) * (N + 1));
int i = 1;
while (fscanf(fp, "%d %d", &matric[i].key1, &matric[i].key2) != EOF)
i++;
fclose(fp);
}
void COLOR(int color)
{
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), color);
}
void Init(element temp[])
{
for (int i = 1; i <= N; i++)
{
temp[i] = matric[i];
}
}
void heapSort(element a[], int n, int key)
{
int i;
element temp;
for (i = n / 2; i >0; i--)
adjust(a, i, n, key);
COLOR(13);
printf("==Initial Heap==\n");
COLOR(15);
Print(a); //출력
for (i = n - 1; i >0; i--)
{
SWAP(a[1], a[i + 1], temp);
adjust(a, 1, i, key);
}
COLOR(11);
printf("==Heap Sort==\n");
COLOR(15);
Print(a); //출력
}
void adjust(element a[], int root, int n, int key)
{
int child, rootkey;
element temp;
temp = a[root];
if (key == 1) { //key1 기준
rootkey = a[root].key1;
child = 2 * root;
while (child <= n) {
if ((child < n) && (a[child].key1 < a[child + 1].key1))
child++;
if (rootkey >= a[child].key1)
break;
else {
a[child / 2] = a[child];
child *= 2;
}
}
a[child / 2] = temp;
}
else { //key2 기준
rootkey = a[root].key2;
child = 2 * root;
while (child <= n) {
if ((child < n) && (a[child].key2 < a[child + 1].key2))
child++;
if (rootkey >= a[child].key2)
break;
else {
a[child / 2] = a[child];
child *= 2;
}
}
a[child / 2] = temp;
}
}
void Print(element a[])
{
for (int i = 1; i <= N; i++)
printf("%d %d\n", a[i].key1, a[i].key2);
printf("\n");
}출력값
정렬 알고리즘 관련 글