[컴퓨터공학] 3-way 외부 합병 정렬

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[])
버…

① 비어있는 버퍼에는 ‘-1’로 채운다는 것.

② 여러 횟수의 사이클(cycle)이 한 단계의 스텝(step)을 구성한다는 것.

③ 각 스텝에는 스텝에 해당하는 고유 번호(number)가 있다는 것.

④ 하나의 버퍼를 다 썼으면 ③번 규칙으로 구한 number 만큼 다음 버퍼로 넘어갈 때 fseek()로 넘어간다.

이다.

①번 규칙은 init() 함수가 역할을 담당한다. flush() 함수로 데이터를 output.txt 파일에 출력할 때에도, isfull() 함수로 버퍼가 가득 찼는지 체크할 때에도, compare() 함수로 최솟값을 구할 때에도 아주 유용하게 사용된다.