Max-Heap을 이용하여 Heapsort를 수행하는 프로그램

소개글

Max-Heap을 이용하여 Heapsort를 수행하는 프로그램에 대한 보고서 자료입니다.

목차

1. 문제

2. 입출력의 예

3. 알고리즘

4. source code

5. 실행결과

본문내용

e 50:
fp= fopen("data50.txt", "r");
break;
case 100:
fp= fopen("data100.txt", "r");
break;
case 500:
fp= fopen("data500.txt", "r");
break;
case 1000:
fp= fopen("data1000.txt", "r");
break;
case 5000:
fp= fopen("data5000.txt", "r");
break;
case 10000:
fp= fopen("data10000.txt", "r");
break;
default:
printf("%d개의 데이터 파일은 없습니다.\n",n);
break;
}
for(i=1; i<= n ;i++) //list라는 배열에 데이터값을 넣는다.
fscanf(fp,"%f",&list[i]);
heapsort (n); //n개의 데이터에 대한 heapsort함수 호출
if(n>=500) //데이터의 크기가 500보다 클때 앞뒤로 30개씩 출력한다.
{
for(i = 1 ; i <= 30 ; i++)
{
if(i % 5 == 0) printf("%10.4f \n", list[i]); //출력할때 줄을 맞추기 위해서
//"%10.4f "를 썼다.
else
{
printf("앞의 30개의 결과\n");
printf("%10.4f " , list[i]);
}
}
for(i = n-29 ; i <= n ; i++)
{
if(i % 5 == 0) printf("%10.4f \n", list[i]);
else
{
printf("뒤의 30개의 결과\n");
printf("%10.4f " , list[i]);
}
}
}
else
{
printf("정렬결과\n");
for(i = 1 ; i <= n ; i++)
{
if(i % 5 == 0) printf("%10.4f \n", list[i]);
else printf("%10.4f " , list[i]);
}
}
fclose(fp); //열었던 데이터 파일을 닫는다.
}
// 최대힙을 구성하기 위한 함수
void adjust( int root,int n)
{
float rootkey,temp;
int child;
temp = list[root];
rootkey = list[root];
child = 2*root; // 왼쪽 자식
while(child <= n) {
if((child < n) && (list[child] < list[child+1]))
child++;
if(rootkey > list[child])
break;
else {
list[child / 2] = list[child];
child *= 2;
}
}
list[child / 2] = temp;
}
//배열에 대한 힙정렬을 수행하는 함수
void heapsort(int n)
{
int i,j ;
for(i = n/2 ; i > 0 ; i--)
adjust( i , n); //adjust를 이용하여 최대힙을 구축
for(j = n-1 ; j > 0 ; j--)
{
swap(&list[1], &list[j+1]); //루트의 자리 교환
adjust( 1, j); //루트의 자리 교환후 힙 재구성
}
}
void swap( float *a, float *b)
{
float temp;
temp=*a;
*a=*b;
*b=temp;
}
5. 실행결과
(1) 데이터의 수가 10개일때
(2) 데이터의 수가 20개일때
(3) 데이터의 수가 50개일때
(4) 데이터의 수가 100개일때
(5) 데이터의 수가 500개일 때
(6) 데이터의 수가 1000개일때
(7) 데이터의 수가 5000개일 때
(8) 데이터의 수가 10000개일 때
6. 결과분석 및 토의
처음 프로그램을 돌려보니 heapsort함수에 두 번에 for문이 잘 작동(?)하지 않았다. 왜그런지 알고보니 swap 함수에서 간단한 포인터를 실수한 것이었다. 그 부분만 고치니 잘 돌아가서 기분이 좋았다. 또 main 함수에서 결과를 출력하는 printf문에서 %f를 사용하니 8.98 같은 숫자가 8.97999 이런식으로 출력이 되었다. 그래서 %.4f로 쓰니 해결이 되었다. 그리고 출력할 때 자리수를 맞추기 위해서 %10.4f를 썼다. 자료구조 수업 때문에 자료구조와 알고리즘의 이론만 배우는게 아니라 c언어도 공부할수 있어서 좋다. 그리고 dos창이 20여줄밖에 되지 않아서 출력결과를 앞 뒤 30개로 하기위해서 한줄에 5개씩 출력하였다. 재미있는 숙제였다.

키워드

max,   heap,   heapsorting,   오름차순,   배열