ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 정렬 합병 #1. 대체 선택
    Programming/College 2010. 6. 18. 13:33
    728x90
    반응형
    SMALL

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

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


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

    댓글

Designed by Tistory.