3-way 외부 합병 정렬
1. 프로젝트 설명
순차파일(binary형태)로 주어지는 데이터 파일(.dat)에서 킷값에 해당 하는 부분을 가지고 정렬을 실행한다.
3-way 외부 합병정렬을 구현하는데, 버퍼의 크기는 버퍼1, 2, 3은 각각 1KBytes이고, 출력에 쓰이는 버퍼(out[])도 1KBytes이다. 출력버퍼가 가득 차면 임시파일(temp1.txt, temp2.txt)에 binary 형태로 Write 하고, 버퍼를 비운 후에 다시 채워가면서 Merge Sorting 하는 프로그램을 구현하는 것이다. Merge Sorting은 각 단계(step)별로 수행된다.
Merge Sorting 되는 방식은 아래 그림과 같다.
버퍼를 Sorting 하는 방식은 개발자(developer) 임의로 정해서 구현한다.
2. 프로젝트 구현
다음은 이번 프로젝트 구현에 있어서 임의로 정의한 함수에 대한 설명이다.
int partition(int list[], int left, int right)
버퍼(list[])를두 부분으로 파티션 하는 함수. quick_sort()에서 사용된다.
void quick_sort(int list[], int left, int right)
버퍼(list[])에 저장된 키 값을 퀵정렬(quick-sort)로 정렬하는 함수.
int compare(int a, int b, int c)
a, b, c 중에 최솟값을 구하는 함수.
int oddeven(int x)
x가 홀수인지 짝수인지 구별하는 함수(짝수 : return 0, 홀수 : return 1)
void init(int buf[])
버퍼를 초기화한다. 즉 버퍼의 내용을 -1로 채운다.
void flush(FILE *out, int buf[])
버퍼를 출력하고 비우는 함수
int isfull(int buf[])
버퍼가 가득 찼는지 체크하는 함수(가득차면 return 1, 그렇지 않으면 return 0)
.... |
2011.04.29
5페이지
