3원다단계합병알고리즘구현

소개글

3원다단계합병알고리즘구현에 대한 보고서 자료입니다.

목차

1.과제 설명

2.프로그램 설명

3.3원 다단계 합병 알고리즘 구현에 이용된 함수 설명

4.프로그램 실행 과정 설명

5.프로그램 소스 파일 첨부 및 설명

본문내용

되고
fp[3].pnt=fopen(fp[3].name,"r");//처리된 런을 저장한 파일이 다음 단계의 입력파일이 되는 것이다.
tfp=fp[3].pnt;//다음 단계 합병을 위해서 파일들을 조정한다.
tname=(char*)malloc(sizeof("temp3.txt"));//교재에 나온 알고리즘을 그대로 이용하였다.
strcpy(tname,fp[3].name);//즉 fp[0],fp[1],fp[2]가 가리키는 파일이 항상 입력 파일이고
tnum=fp[3].fnum;//fp[3]이 가리키는 파일이 항상 출력 파일이 되도록
trun=fp[3].run;//파일들을 재할당 하는 부분이다.
for(i=3;i>0;i--){//파일 구조체의 모든 멤버 변수를 모두 바꿔주어야 한다.
fp[i].pnt=fp[i-1].pnt;
strcpy(fp[i].name,fp[i-1].name);//임시변수에 fp[3]의 정보를 모두 저장해놓고
fp[i].fnum=fp[i-1].fnum;//fp[3]에 fp[2]의 정보를
fp[i].run=fp[i-1].run;//fp[2]에 fp[1]의 정보를
}//fp[1]에 fp[0]의 정보를 저장하고
fp[0].pnt=tfp;//fp[0]에 임시 변수의 내용(fp[3])을 저장한다.
strcpy(fp[0].name,tname);
fp[0].fnum=tnum;
fp[0].run=trun;
pass_count++;
}
////////이while문이 끝남과 동시에 3원 다단계 합병이 사실상 끝났다고 할 수 있다.
//합병된 결과는 fp[3]이 가리키는 파일에 한개의 런(크기가 1000)으로 들어가 있다.
rewind(fp[3].pnt);//정렬 결과를 output.txt에 다시 출력 하기 위해서 fp[3]파일을 읽어야 한다.
for(i=0;i<4;i++){//합병에 사용된 임시 파일 4개를 닫는다.
fclose(fp[i].pnt);
free(fp[i].name);
}
tfp=fopen("temp3.txt","r");//합병 결과가 있는 파일을 열어서
result_fp=fopen("output.txt","w");
fscanf(tfp,"%d",&m);//처음 정수는 런의 크기를 나타내므로 무시하고
for(i=0;i<1000;i++){
fscanf(tfp,"%d",&m);//그 다음부터 1000개의 정렬된 정수를 읽어서
fprintf(result_fp,"record%5d => %5d\n",i+1,m);//output.txt파일에 출력한다.
}
fclose(tfp);//열린 파일 닫기
fclose(result_fp);
fclose(mid_fp);
//윈도우에서 코딩 및 테스트를 하였다.
system("del temp0.txt");//dos 시스템 명령을 사용하여 임시 파일을 지운다.
system("del temp1.txt");//dos나 window에서 실행할 경우
system("del temp2.txt");
system("del temp3.txt");
//system("rm temp0.txt");//unix 시스템일 경우
//system("rm temp1.txt");
//system("rm temp2.txt");
//system("rm temp3.txt");
}
void mergeRun(FILE *mid_fp){//각 입력 파일에서 런을 하나씩 읽어 런에 포함된 레코들을 합병한 후
int i=0,j=0,k=0,s[3]={0,0,0},*tmpd;//출력 파일에 써넣는 함수
for(i=0;i<3;i++)//우선 각 입력 파일에서 런의 크기를 읽는다.
fscanf(fp[i].pnt,"%d",&s[i]);
tmpd=(int*)malloc(sizeof(int)*(s[0]+s[1]+s[2]));//세 입력 파일에서 읽은 런의 레코드들을 저장할 변수 메모리할당
fprintf(mid_fp," %4d %4d %4d | ",s[0],s[1],s[2],s[0]+s[1]+s[2]);//중간 과정 intermed.txt에 출력
for(j=0;j<3;j++)//각 입력 파일에서 런의 레코드들을 읽어서
if(s[j]!=0)//임시 변수에 저장
for(i=0;i fscanf(fp[j].pnt,"%d",&tmpd[k++]);
quickSort(tmpd,k);//임수 변수에 저장된 레코드들을 퀵소트로 정렬한다.
fprintf(fp[3].pnt,"\n%d ",s[0]+s[1]+s[2]);//출력파일에 런의 크기를 먼저 출력하고
fprintf(mid_fp,"%d ",s[0]+s[1]+s[2]);//중간 과정 intermed.txt에도 출력하고
for(i=0;i fprintf(mid_fp,"%d ",tmpd[i]);//"런의 크기+공백+레코드+공백+...+마지막레코드" 형식을 맞추기 위해
fprintf(fp[3].pnt,"%d ",tmpd[i]);
}
fprintf(mid_fp,"%d \n",tmpd[i]);//for문이 끝나고 마지막 레코드 출력
fprintf(fp[3].pnt,"%d",tmpd[i]);
}
void quickSort(int *tmpd, int num){//퀵소트하는 함수
int left,right,key,tmp;
if (num <= 1) return;//구간이 1이면 정렬을 끝낸다.
key=tmpd[num-1];// 기준값 결정 : 배열상의 제일 끝 요소
for (left=0,right=num-2;;left++,right--){
while(tmpd[left] while(tmpd[right]>key) {right--;}
if(left>=right) break;// 좌우가 만나면 끝
tmp=tmpd[left];
tmpd[left]=tmpd[right];
tmpd[right]=tmp;
}
tmp=tmpd[left];// 기준값과 i위치의 값 교환
tmpd[left]=tmpd[num-1];
tmpd[num-1]=tmp;
quickSort(tmpd,left);// 왼쪽 구간 정렬
quickSort(tmpd+left+1,num-left-1);// 오른쪽 구간 정렬
}

키워드

다단계,   합병,   알고리즘,   multiphase,   merge,   algorithm