티스토리 뷰

Programming/College

정렬 합병 #1. 대체 선택

다재다능한 StomX 2010.06.18 13:33

정렬되지 않은 데이터를 정렬시키면서 하나의 파일에 합병하기 위해 대체선택으로 Run[각주:1]을 생성해야한다.

▣ 대체선택의 런 생성 방법
1. 버퍼에 입력 파일로부터 m개의 레코드를 읽어와서 첫 번째 런을 생성한다.
2. 버퍼에서 키 값이 가장 작은 레코드를 선택하여 출력한다.
3. 입력 파일로부터 다음 레코드를 읽어와서 출력된 레코드와 대체시킨다.
   이 때 만일 읽어온 키 값이 출력된 키 값보다 작으면 읽어온 키 값에 "동결(Frozen)" 표시.
   동결된 레코드는 단계②에서 제외된다.
   아직 동결되지 않은 레코드가 있으면 단계②로 되돌아간다.
4. 동결된 레코드들을 모두 해제하고 단계②로 돌아가 새로운 런을 생성한다.

대체선택 알고리즘 펼치기


이 대체 선택 방법이 입력 파일의 일부 정렬된 레코드들의 순서를 이용한다는 것은 분명하다. 입력 파일에 정렬된 레코드가 많으면 많을수록 한 개의 Run에 입력되는 레코드의 개수는 증가하게 된다.
이 방법을 이용했을 때 Run의 평균 예상 길이는 2m 레코드가 된다고 알려져 있다.
  1. 다수의 레코드를 가지고 있는 파일을 n개의 서브파일로 나누어 이들에 각각 내부 정렬 기법을 적용한 것. [본문으로]
댓글